Combination Sum
Problem Statement
You are given an array of distinct integers nums
and a target integer target
. Your task is to return a list of all unique combinations of nums
where the chosen numbers sum to target
.
The same number may be chosen from nums
an unlimited number of times. Two combinations are the same if the frequency of each of the chosen numbers is the same, otherwise they are different.
You may return the combinations in any order and the order of the numbers in each combination can be in any order.
Example 1:
Input:nums = [2,5,6,9]target = 9
Output: [[2,2,5],[9]]
Explanation: 2 + 2 + 5 = 9. We use 2 twice, and 5 once. 9 = 9. We use 9 once.
Example 2:
Input:nums = [3,4,5]target = 16
Output: [[3,3,3,3,4],[3,3,5,5],[4,4,4,4],[3,4,4,5]]
Example 3:
Input:nums = [3]target = 5
Output: []
Constraints:
- All elements of
nums
are distinct. 1 <= nums.length <= 20
2 <= nums[i] <= 30
2 <= target <= 30
You should aim for a solution with O(2^{t/m})
time and O(t/m)
space, where t
is the given target
and m
is the minimum value in the given array.
Recommended Time and Space Complexity
You should aim for a solution with O(2^{t/m})
time and O(t/m)
space, where t
is the given target
and m
is the minimum value in the given array.
Hint 1
Can you think of this problem in terms of a decision tree, where at each step, we have n
decisions, where n
is the size of the array? In this decision tree, we can observe that different combinations of paths are formed. Can you think of a base condition to stop extending a path? Maybe you should consider the target value.
Hint 2
We can use backtracking to recursively traverse these paths and make decisions to choose an element at each step. We maintain a variable sum
, which represents the sum of all the elements chosen in the current path. We stop this recursive path if sum == target
, and add a copy of the chosen elements to the result. How do you implement it?
Hint 3
We recursively traverse the array starting from index i
. At each step, we select an element from i
to the end of the array. We extend the recursive path with elements where sum <= target
after including that element. This creates multiple recursive paths, and we append the current list to the result whenever the base condition is met.
Solution
Backtracking
def combination_sum(nums: List[int], target: int) -> List[List[int]]: result = []
def dfs(i, current, total): if total == target: result.append(current.copy()) return if i >= len(nums) or total > target: return
current.append(nums[i]) dfs(i, current, total + nums[i]) current.pop() dfs(i + 1, current, total)
dfs(0, [], 0) return result
Time complexity: O(2^{t/m})
Space complexity: O(t/m)
Backtracking (Optimal)
def combination_sum_optimal(nums: List[int], target: int) -> List[List[int]]: result = [] nums.sort()
def dfs(i, current, total): if total == target: result.append(current.copy()) return
for j in range(i, len(nums)): if total + nums[j] > target: return current.append(nums[j]) dfs(j, current, total + nums[j]) current.pop()
dfs(0, [], 0) return result
Time complexity: O(2^{t/m})
Space complexity: O(t/m)