39. Combination Sum
## description
## 39. Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
1Input: candidates = [2,3,6,7], target = 7
2Output: [[2,2,3],[7]]
3Explanation:
42 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
57 is a candidate, and 7 = 7.
6These are the only two combinations.Example 2:
1Input: candidates = [2,3,5], target = 8
2Output: [[2,2,2,2],[2,3,3],[3,5]]Example 3:
1Input: candidates = [2], target = 1
2Output: []- –1 <= candidates.length <= 30
- –2 <= candidates[i] <= 40
- –All elements of candidates are distinct.
- –1 <= target <= 40
Constraints:
## notes
### Intuition
For each number, we have two choices; use it again or skip it.
### Implementation
Since we have two choices for each number and we want to explore all possible branches of this decision tree for each number, we can solve this using recursive back tracking.
We set up or recursive function to take in the index for the candidates, i, the current set of numbers, curr, and the current total. Our first base case is to check if the total is equal to the target, that means our curr is a set of numbers that adds up to the same so we addit to our result and return early. Our second base case is when i exceeds the bounds or if the total exceeds the target, this is now an invalid set or recursive parameters so we return early.
Now, for our two cases, the first case is to add the same number again. We add the number to curr and recurse with the same i and number added to the total. The second case is to skip the current number, so we pop from curr (because we just added it in the first case) and recurse with i + 1 and the same total. We keep the total the same in the second case because adding to the total is handled by the first case, on the first time seeing a number it will be called with the first case of "using the same number again".
- –Time: O(2^(t/m)), where t is the target and m is the smallest number in candidates. The worst-case is choosing the same number each time which will cause a recursion stack of t/m because each m will reduce t by m.
- –Space: O(t/m), recursion stack.
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
5 res = []
6 def recurse(i: int, curr: List[int], total: int):
7 if total == target:
8 res.append(curr.copy())
9 return
10 if i >= len(candidates) or total > target:
11 return
12
13 curr.append(candidates[i])
14
15 # Case 1: add the current number again (duplicates allowed)
16 recurse(i, curr, total + candidates[i])
17
18 # Case 2: Skip the current number
19 curr.pop()
20 recurse(i + 1, curr, total)
21
22
23 recurse(0, [], 0)
24 return res
25
26
27
28if __name__ == "__main__":
29 # Include one-off tests here or debugging logic that can be run by running this file
30 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
31 solution = Solution()
32