We use backtracking to try including or excluding each element. We prune branches where the current sum exceeds the target.
- Sort the array for easier pruning.
- For each element, include it in the current subset and reduce the target.
- If target becomes 0, save the subset.
- If target goes negative, backtrack.
- Skip to the next element to explore other subsets.
- Time Complexity: O(2^N).
- Space Complexity: O(N).
def subset_sum(nums, target):
result = []
nums.sort()
def backtrack(start, current, remaining):
if remaining == 0:
result.append(current[:])
return
for i in range(start, len(nums)):
if nums[i] > remaining:
break
current.append(nums[i])
backtrack(i + 1, current, remaining - nums[i])
current.pop()
backtrack(0, [], target)
return result