숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, 리스트의 요소들 중 합이 정확히 k가 되는 부분 집합(subset)의 개수를 구하는 문제입니다. 답이 매우 커질 수 있으므로 결과는 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력이 nums = [2, 3, 4, 5, 7], k = 7이라면 출력은 3이 됩니다. [2, 5], [3, 4], [7] 세 가지 부분 집합을 만들 수 있기 때문입니다.
문제 해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 각 단계는 다음과 같습니다.
- 크기가 (k + 1)인 리스트 dp를 만들고 모든 값을 0으로 초기화합니다.
- dp[0]을 1로 설정합니다. (아무것도 선택하지 않는 공집합의 합은 0이므로 경우의 수가 1)
- m := 10^9 + 7로 설정하여 값이 너무 커지는 것을 방지합니다.
- i를 0부터 len(nums) - 1까지 반복합니다.
- j를 k부터 0까지 1씩 감소시키며 반복합니다.
- nums[i] <= j인 경우 다음을 수행합니다.
- dp[j] := dp[j] + dp[j - nums[i]]
- dp[j] := dp[j] mod m
핵심 포인트: 내부 루프를 k에서 0으로 역방향으로 순회하는 이유는 같은 요소를 여러 번 재사용하는 것을 방지하기 위해서입니다. 만약 정방향으로 순회하면 하나의 숫자를 중복해서 더하는 경우가 발생하여, 부분 집합이 아닌 '중복을 허용하는 조합'을 세게 됩니다.
마지막으로 dp[k] mod m을 반환하면 원하는 답을 얻을 수 있습니다.
구현 예제
class Solution: def solve(self, nums, k): dp = [0] * (k + 1) dp[0] = 1 m = int(1e9 + 7) for i in range(len(nums)): for j in range(k, -1, -1): if nums[i] <= j: dp[j] += dp[j - nums[i]] dp[j] %= m return dp[k] % m ob = Solution() nums = [2, 3, 4, 5, 7] k = 7 print(ob.solve(nums, k))
입력
[2, 3, 4, 5, 7], 7
출력
3
복잡도 분석
시간 복잡도는 O(n × k)(n은 리스트의 길이), 공간 복잡도는 O(k)입니다. 모든 부분 집합을 일일이 확인하는 완전 탐색 방식(O(2^n))보다 훨씬 효율적이므로, n과 k가 큰 입력에서도 빠르게 동작합니다.