← 4주차 · 완전탐색과 시뮬레이션
보통완전탐색비트마스크

부분집합의 합

정수 배열 nums와 정수 target이 주어져요. 원소의 합이 target이 되는 공집합이 아닌 부분집합의 개수를 반환해요.

값이 같아도 인덱스가 다르면 다른 부분집합이에요. 예를 들어 nums = [1, 1] 에서 합이 1인 부분집합은 두 개예요.

원소가 n개면 부분집합은 2ⁿ개예요. 0부터 2ⁿ - 1까지의 정수 하나하나를 어떤 원소를 골랐는지 나타내는 비트열로 보면, 반복문 하나로 모든 부분집합을 훑을 수 있어요. i번 비트가 켜져 있는지는 mask & (1 << i) 로 확인해요.

예시

예시 1
입력
nums = [1, 2, 3], target = 3
출력
2
설명
{3} 과 {1, 2} 두 가지예요.
예시 2
입력
nums = [1, 1, 1], target = 2
출력
3
설명
인덱스 기준으로 (0,1), (0,2), (1,2) 세 가지예요.
예시 3
입력
nums = [5], target = 3
출력
0

제한 사항

  • 1 ≤ nums.length ≤ 15
  • -1,000 ≤ nums[i] ≤ 1,000
  • -15,000 ≤ target ≤ 15,000
for (let mask = 1; mask < (1 << n); mask++) 로 돌면 공집합인 0을 자연스럽게 건너뛰어요. 안쪽에서 i번 비트가 켜졌는지 확인하며 합을 만들어요. 1 << 15 는 32,768 이라 전부 훑어도 순식간이에요.
javascript
function subsetSum(nums, target) {
  const n = nums.length;
  let count = 0;
  for (let mask = 1; mask < (1 << n); mask++) {
    let sum = 0;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) sum += nums[i];
    }
    if (sum === target) count++;
  }
  return count;
}
이전 문제세 수의 합
다음 문제행렬 90도 회전
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.