Combination Sum
MedPrompt
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] <= 40- All elements of
candidatesare distinct. 1 <= target <= 40
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a classic recursive backtracking algorithm to find all possible combinations. The core idea is to build a combination step-by-step. At each step, we try to add a candidate number to the current combination and then recursively call the function with the updated target. If the target becomes zero, we've found a valid combination. If it becomes negative, we backtrack. To handle duplicates and the fact that numbers can be reused, we control the search by only considering candidates from the current index onwards.
Algorithm
- Initialize an empty list
resultsto store the final combinations. - Define a recursive helper function
backtrack(candidates, remaining, currentCombination, results, start). - Base Case 1: If
remainingis 0, add a copy ofcurrentCombinationtoresultsand return. - Base Case 2: If
remainingis less than 0, this path is invalid, so return. - Recursive Step: Iterate through
candidatesfrom thestartindex.- Add the current candidate
candidates[i]tocurrentCombination. - Make a recursive call:
backtrack(candidates, remaining - candidates[i], currentCombination, results, i). We passias the start index to allow reusing the same element. - Remove the last element from
currentCombinationto backtrack.
- Add the current candidate
- Call the initial
backtrackfunction withtarget, an empty combination,results, andstartindex 0. - Return
results.
Walkthrough
The algorithm is implemented with a helper function, say backtrack, which takes the remaining target, the current combination being built, and a starting index for the candidates array.
The process is as follows:
- The main function initializes an empty list for the results and calls the
backtrackhelper function. - The
backtrackfunction checks for two base cases:- If the remaining target is 0, a valid combination has been found. A copy of the current combination is added to the results list.
- If the remaining target is negative, the current path is invalid, and the function returns, effectively pruning this branch.
- If neither base case is met, the function iterates through the
candidatesarray, starting from thestartindex. For each candidate:- It adds the candidate to the current combination.
- It makes a recursive call to itself with the updated target (
remaining - candidate) and the samestartindex (i). Passingiinstead ofi + 1allows the same number to be reused in the combination. - After the recursive call returns, it removes the last added candidate. This is the "backtracking" step, which allows exploration of other possibilities.
Using a start index ensures that we generate unique combinations (e.g., [2, 2, 3]) and not their permutations (e.g., [2, 3, 2])
import java.util.ArrayList;import java.util.List; class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> results = new ArrayList<>(); backtrack(candidates, target, new ArrayList<>(), results, 0); return results; } private void backtrack(int[] candidates, int remaining, List<Integer> currentCombination, List<List<Integer>> results, int start) { if (remaining < 0) { return; } if (remaining == 0) { results.add(new ArrayList<>(currentCombination)); return; } for (int i = start; i < candidates.length; i++) { currentCombination.add(candidates[i]); // Pass 'i' as the next start index to allow reusing the same element backtrack(candidates, remaining - candidates[i], currentCombination, results, i); // Backtrack currentCombination.remove(currentCombination.size() - 1); } }}Complexity
Time
O(N^(T/M)) where N is the number of candidates, T is the target, and M is the minimum value in candidates. This represents the number of nodes in the recursion tree.
Space
O(T/M) where T is the target and M is the minimum candidate value. This corresponds to the maximum depth of the recursion stack.
Trade-offs
Pros
Conceptually simple and directly follows the problem's recursive nature.
Guarantees finding all possible combinations.
Cons
Can be inefficient as it may explore many branches that will inevitably exceed the target.
Time complexity is exponential, making it slow for larger inputs (though it's acceptable for the given constraints).
This approach enhances the basic backtracking solution by introducing an optimization. By sorting the candidates array first, we can prune the search space more effectively. If adding the current candidate would make the sum exceed the target, we know that adding any subsequent (larger) candidate will also exceed the target. This allows us to stop searching further down that path, reducing the number of recursive calls.
Algorithm
- Sort the
candidatesarray. - Initialize an empty list
results. - Define a recursive helper function
backtrack(candidates, remaining, currentCombination, results, start). - Base Case: If
remainingis 0, add a copy ofcurrentCombinationtoresultsand return. - Recursive Step: Iterate through
candidatesfrom thestartindex.- Pruning: If
remaining < candidates[i], break the loop. Since the array is sorted, no further candidate will form a valid combination. - Add the current candidate
candidates[i]tocurrentCombination. - Make a recursive call:
backtrack(candidates, remaining - candidates[i], currentCombination, results, i). - Remove the last element from
currentCombinationto backtrack.
- Pruning: If
- Call the initial
backtrackfunction. - Return
results.
Walkthrough
The core logic remains the same as the brute-force backtracking approach, but with a key improvement.
The steps are:
- First, sort the
candidatesarray in non-decreasing order. This is crucial for the pruning optimization. - The
backtrackhelper function is called, similar to the previous approach. - Inside the
backtrackfunction's loop, before making a recursive call, we add a check. - Because the array is sorted, if
remaining < candidates[i], it means the current candidatecandidates[i]is too large. All subsequent candidates (candidates[i+1],candidates[i+2], etc.) will also be too large. - Therefore, we can
breakout of the loop, effectively pruning a significant portion of the recursion tree and avoiding unnecessary computations.
This simple optimization can lead to a substantial performance improvement, especially when the target is relatively small compared to some of the candidate numbers.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> results = new ArrayList<>(); // Sort the candidates to enable pruning Arrays.sort(candidates); backtrack(candidates, target, new ArrayList<>(), results, 0); return results; } private void backtrack(int[] candidates, int remaining, List<Integer> currentCombination, List<List<Integer>> results, int start) { if (remaining == 0) { results.add(new ArrayList<>(currentCombination)); return; } for (int i = start; i < candidates.length; i++) { // Pruning step if (remaining < candidates[i]) { // If the current candidate is greater than the remaining target, // all subsequent candidates will also be greater, so we can stop. break; } currentCombination.add(candidates[i]); // Pass 'i' as the next start index to allow reusing the same element backtrack(candidates, remaining - candidates[i], currentCombination, results, i); // Backtrack currentCombination.remove(currentCombination.size() - 1); } }}Complexity
Time
O(N log N + N^(T/M)), where the O(N log N) is for sorting. The backtracking complexity remains exponential in the worst case but is faster on average.
Space
O(T/M) for the recursion stack depth. Sorting might take O(log N) or O(N) auxiliary space depending on the implementation.
Trade-offs
Pros
More efficient than the basic backtracking approach due to search space pruning.
It is the standard and most common solution for this type of problem.
Maintains the conceptual simplicity of backtracking.
Cons
The worst-case time complexity is still exponential.
Requires an initial sorting step, which adds an O(N log N) cost.
Solutions
Solution
public class Solution { private List < IList < int >> ans = new List < IList < int >> (); private List < int > t = new List < int > (); private int[] candidates; public IList < IList < int >> CombinationSum(int[] candidates, int target) { Array.Sort(candidates); this.candidates = candidates; dfs(0, target); return ans; } private void dfs(int i, int s) { if (s == 0) { ans.Add(new List < int > (t)); return; } if (i >= candidates.Length || s < candidates[i]) { return; } dfs(i + 1, s); t.Add(candidates[i]); dfs(i, s - candidates[i]); t.RemoveAt(t.Count - 1); }}class Solution { private List < List < Integer >> ans = new ArrayList <>(); private List < Integer > t = new ArrayList <>(); private int [] candidates ; public List < List < Integer >> combinationSum ( int [] candidates , int target ) { Arrays . sort ( candidates ); this . candidates = candidates ; dfs ( 0 , target ); return ans ; } private void dfs ( int i , int s ) { if ( s == 0 ) { ans . add ( new ArrayList ( t )); return ; } if ( i >= candidates . length || s < candidates [ i ]) { return ; } dfs ( i + 1 , s ); t . add ( candidates [ i ]); dfs ( i , s - candidates [ i ]); t . remove ( t . size () - 1 ); } } ////// class Solution_dp { public List < List < Integer >> combinationSum ( int [] candidates , int target ) { // for each-target (from 1 to target), its dp[i][j] => so 3-D array dp[][][] List < List < List < Integer >>> dp = new ArrayList <>(); Arrays . sort ( candidates ); for ( int i = 1 ; i <= target ; ++ i ) { List < List < Integer >> cur = new ArrayList <>(); for ( int j = 0 ; j < candidates . length ; ++ j ) { if ( candidates [ j ] > i ) break ; if ( candidates [ j ] == i ) { ArrayList < Integer > one = new ArrayList < Integer >(); one . add ( candidates [ j ]); cur . add ( one ); // @note: one with proper <Integer>, or else unsupoorted operation error break ; } for ( List < Integer > a : dp . get ( i - candidates [ j ] - 1 )) { if ( candidates [ j ] > a . get ( 0 )) { continue ; } ArrayList < Integer > deepCopied = new ArrayList <>( a ); // @note: must have deepCopied . add ( 0 , candidates [ j ]); // @note: largest at index=0 for the array cur . add ( deepCopied ); } } dp . add ( cur ); } return dp . get ( dp . size () - 1 ); } }class Solution { public: vector < vector < int >> combinationSum ( vector < int >& candidates , int target ) { sort ( candidates . begin (), candidates . end ()); vector < vector < int >> ans ; vector < int > t ; function < void ( int , int ) > dfs = [ & ]( int i , int s ) { if ( s == 0 ) { ans . emplace_back ( t ); return ; } if ( i >= candidates . size () || s < candidates [ i ]) { return ; } dfs ( i + 1 , s ); t . push_back ( candidates [ i ]); dfs ( i , s - candidates [ i ]); t . pop_back (); }; dfs ( 0 , target ); return ans ; } };class Solution : def combinationSum ( self , candidates : List [ int ], target : int ) -> List [ List [ int ]]: # i: start index for this recursion # s: sum def dfs ( i , s ): if s == target : ans . append ( t . copy ()) return if s > target : return for j in range ( i , len ( candidates )): c = candidates [ j ] t . append ( c ) dfs ( j , s + c ) t . pop () ans = [] t = [] # candidates.sort() # diff from combinationSum-II, no need sorting it dfs ( 0 , 0 ) return ans ############ # dp version class Solution_dp : def combinationSum ( self , candidates : List [ int ], target : int ) -> List [ List [ int ]]: # for each-target (from 1 to target), its dp[i][j] # => so 3-D array dp[][][] dp = [] candidates . sort () for i in range ( 1 , target + 1 ): cur = [] for j in range ( len ( candidates )): if candidates [ j ] > i : break if candidates [ j ] == i : one = [ candidates [ j ]] cur . append ( one ) break for a in dp [ i - candidates [ j ] - 1 ]: if candidates [ j ] > a [ 0 ]: continue deepCopied = a . copy () deepCopied . insert ( 0 , candidates [ j ]) cur . append ( deepCopied ) dp . append ( cur ) return dp [ - 1 ] ############ class Solution ( object ): def combinationSum ( self , candidates , target ): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ def dfs ( candidates , start , target , path , res ): if target == 0 : return res . append ( path + []) for i in range ( start , len ( candidates )): if target - candidates [ i ] >= 0 : path . append ( candidates [ i ]) dfs ( candidates , i , target - candidates [ i ], path , res ) path . pop () res = [] dfs ( candidates , 0 , target , [], res ) return res ######### class Solution : def combinationSum ( self , candidates : List [ int ], target : int ) -> List [ List [ int ]]: def dfs ( i : int , s : int ): if s == 0 : ans . append ( t [:]) return if i >= len ( candidates ) or s < candidates [ i ]: return dfs ( i + 1 , s ) t . append ( candidates [ i ]) dfs ( i , s - candidates [ i ]) t . pop () candidates . sort () t = [] ans = [] dfs ( 0 , target ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.