Combination Sum
Problem Statement
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.
Constraints:
- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- All elements of candidates are distinct.
- 1 <= target <= 500
Input Format:
- An array of distinct integers candidates
- A target integer target
Output Format:
- Return a list of all unique combinations of candidates where the chosen numbers sum to target.
Examples:
Example 1:
Input:
candidates = [2,3,6,7], target = 7
Output:
[[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7.
Example 2:
Input:
candidates = [2,3,5], target = 8
Output:
[[2,2,2,2],[2,3,3],[3,5]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 2 + 2 = 8 and 2 + 3 + 3 = 8. 3 and 5 are candidates, and 3 + 5 = 8.
Example 3:
Input:
candidates = [2], target = 1
Output:
[]
Explanation:
There are no candidates that sum to 1.
Solutions
Backtracking Approach
Use a recursive backtracking approach to explore all possible combinations. At each step, we can either include the current number multiple times or move on to the next number.
Dynamic Programming Approach
We can also solve this using dynamic programming by building up solutions from smaller subproblems.
Algorithm Walkthrough
Example input: nums = [], target = 7
Step-by-step execution:
- Initialize an empty result array
- Call backtrack(0, 7, [])
- Start with i=0, candidate=2: path=[2], call backtrack(0, 5, [2])
- i=0, candidate=2: path=[2,2], call backtrack(0, 3, [2,2])
- i=0, candidate=2: path=[2,2,2], call backtrack(0, 1, [2,2,2])
- i=0, candidate=2: path=[2,2,2,2], call backtrack(0, -1, [2,2,2,2]) - invalid, backtrack
- i=1, candidate=3: path=[2,2,3], call backtrack(1, 0, [2,2,3]) - valid solution, add [2,2,3] to result
- Continue backtracking through other paths
- i=3, candidate=7: path=[7], call backtrack(3, 0, [7]) - valid solution, add [7] to result
- Return result [[2,2,3], [7]]
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the backtracking process as a decision tree, showing the exploration of different combinations.
Key visualization elements:
- current path
- remaining target
- decision points
Implementation Notes
This is a classic backtracking problem that illustrates the concept of exploring all possible combinations. Understanding this problem helps with many other recursive and combinatorial problems.