Watch 10 video solutions for Combination Sum, a medium level problem involving Array, Backtracking. This walkthrough by take U forward has 925,071 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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. These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1 Output: []
Constraints:
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates are distinct.1 <= target <= 40Problem Overview: Given an array of distinct integers candidates and a target value, return all unique combinations where the chosen numbers sum to the target. Each number can be used unlimited times. The challenge is generating combinations without duplicates while exploring all valid sums.
Approach 1: Backtracking (Exponential Time, Optimal for Enumeration)
This approach treats the problem as a recursive search tree. Start from index 0, repeatedly choose a candidate, add it to the current combination, and recursively explore the remaining target. If the running sum equals the target, record the combination. If it exceeds the target, stop exploring that path. Because candidates can be reused, the recursive call continues from the same index instead of moving forward.
The key insight is pruning: once the remaining target becomes negative, the branch cannot produce a valid combination. Backtracking efficiently explores possibilities while avoiding unnecessary permutations. Time complexity is exponential, typically O(2^T) in the worst case depending on the target and smallest candidate. Space complexity is O(T) for recursion depth and combination storage. This technique is a classic application of backtracking with recursive exploration over an array.
Approach 2: Dynamic Programming (O(n * target * k))
A dynamic programming strategy builds solutions for every intermediate sum from 0 to target. Use a DP array where dp[i] stores all combinations that produce sum i. Initialize dp[0] with an empty combination. For each candidate number, iterate through target values and extend previously built combinations by appending the candidate.
The advantage of this approach is structured bottom‑up construction. Instead of exploring recursive paths, it reuses previously computed results. Time complexity is roughly O(n * target * k), where n is the number of candidates and k represents the average number of stored combinations. Space complexity is also O(target * k) due to storing all partial combinations. This technique demonstrates a combinational form of dynamic programming.
Recommended for interviews: The backtracking solution is what most interviewers expect. It shows you understand recursive exploration, pruning, and combination generation. Mentioning the dynamic programming variation demonstrates deeper problem-solving breadth, but implementing clean backtracking with correct pruning and duplicate control is usually sufficient for coding interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | Exponential (≈ O(2^T)) | O(T) | Standard interview solution when generating all valid combinations |
| Dynamic Programming | O(n * target * k) | O(target * k) | When you want a bottom-up construction of combinations or reuse intermediate sums |