The brute force solution is just generating all subsets recursively then checking the sum and updating a count. The key observation is that some subproblems overlap. For example, search_subset(target=5) can overlap search_subset(target=4) with and search_subset(target=2). We can give DP a shot.
DP
1. Define by prefix
dp[i][s] = number of subsets that sum to value s using prefix i elements nums[0:i]
(similar to the subset recursive search definition)
2. Solve be prefix
for the current ith element
dp[i][s] = AND(dp[i-1][s], dp[i-1][s-nums[i]])
(not use the current element, use the current element)
3. Base cases
dp[0][0] = 1 (empty subset sums to 0)
4. Topo order
for s from 0 to target
5. Final answer
dp[n][target]
Code
def subset_sum(nums: List[int], target: int) -> int:
n = len(nums)
dp: List[List[int]] = [[0] * (target + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
for s in range(target + 1):
if dp[i][s] == 0:
continue
# not use item i
dp[i + 1][s] += dp[i][s]
# use item i
if s + nums[i] > target:
continue
dp[i + 1][s + nums[i]] += dp[i][s]
return dp[n][target]
The value keys can be sparse. For example, for nums = [1, 100, 1001, 2002], target = 3003 , we don't have to store all the values between 1 to 3003. We only have to store the valid subset sum values in the memoization table. To optimize the data structure for memoization, we can use a nested dictionary rather than a 2D array.
Optimized Code
def subset_sum(nums: List[int], target: int) -> int:
dp: Dict[int, Dict[int, int]] = defaultdict(lambda: defaultdict(int))
dp[0][0] = 1
n = len(nums)
for i in range(n):
for k in dp[i]:
# not use item i
dp[i + 1][k] += dp[i][k]
# use item i
if k + nums[i] > target:
continue
dp[i + 1][k + nums[i]] += dp[i][k]
return dp[n][target]
Time Complexity
min_target = min(2^n, target)
time O(n * min_target) space O(n * min_target)
More Space Optimization
We only have optimized space from the target value dimension so far. We can also optimize the ith element index dimension.
We can see from the recursive step
dp[i][s] = AND(dp[i-1][s], dp[i-1][s-nums[i]])
only depends on the previous index of the state.
We can mod the ith dimension to only store 2 layers of state at a time.
