# Combination Sum **Difficulty:** MEDIUM [External](https://leetcode.com/problems/combination-sum) Canonical: https://scaleengineer.com/dsa/problems/combination-sum **Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking) **Data structures:** Array **Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Airbnb](https://scaleengineer.com/companies/airbnb), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Huawei](https://scaleengineer.com/companies/huawei), [Infosys](https://scaleengineer.com/companies/infosys), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Salesforce](https://scaleengineer.com/companies/salesforce), [Autodesk](https://scaleengineer.com/companies/autodesk), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Snap](https://scaleengineer.com/companies/snap), [Confluent](https://scaleengineer.com/companies/confluent), [Pinterest](https://scaleengineer.com/companies/pinterest) --- ## Problem 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 <= 30` * `2 <= candidates[i] <= 40` * All elements of `candidates` are **distinct**. * `1 <= target <= 40` # Approaches ## Brute-Force Backtracking 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. **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. **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). ### Explanation 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: 1. The main function initializes an empty list for the results and calls the `backtrack` helper function. 2. The `backtrack` function 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. 3. If neither base case is met, the function iterates through the `candidates` array, starting from the `start` index. 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 same `start` index (`i`). Passing `i` instead of `i + 1` allows 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]`) ```java import java.util.ArrayList; import java.util.List; class Solution { public List> combinationSum(int[] candidates, int target) { List> results = new ArrayList<>(); backtrack(candidates, target, new ArrayList<>(), results, 0); return results; } private void backtrack(int[] candidates, int remaining, List currentCombination, List> 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); } } } ``` ### Algorithm * Initialize an empty list `results` to store the final combinations. * Define a recursive helper function `backtrack(candidates, remaining, currentCombination, results, start)`. * **Base Case 1:** If `remaining` is 0, add a copy of `currentCombination` to `results` and return. * **Base Case 2:** If `remaining` is less than 0, this path is invalid, so return. * **Recursive Step:** Iterate through `candidates` from the `start` index. * Add the current candidate `candidates[i]` to `currentCombination`. * Make a recursive call: `backtrack(candidates, remaining - candidates[i], currentCombination, results, i)`. We pass `i` as the start index to allow reusing the same element. * Remove the last element from `currentCombination` to backtrack. * Call the initial `backtrack` function with `target`, an empty combination, `results`, and `start` index 0. * Return `results`. ## Optimized Backtracking with Pruning 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. **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. **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. ### Explanation The core logic remains the same as the brute-force backtracking approach, but with a key improvement. The steps are: 1. First, sort the `candidates` array in non-decreasing order. This is crucial for the pruning optimization. 2. The `backtrack` helper function is called, similar to the previous approach. 3. Inside the `backtrack` function's loop, before making a recursive call, we add a check. 4. Because the array is sorted, if `remaining < candidates[i]`, it means the current candidate `candidates[i]` is too large. All subsequent candidates (`candidates[i+1]`, `candidates[i+2]`, etc.) will also be too large. 5. Therefore, we can `break` out 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. ```java import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public List> combinationSum(int[] candidates, int target) { List> 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 currentCombination, List> 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); } } } ``` ### Algorithm * Sort the `candidates` array. * Initialize an empty list `results`. * Define a recursive helper function `backtrack(candidates, remaining, currentCombination, results, start)`. * **Base Case:** If `remaining` is 0, add a copy of `currentCombination` to `results` and return. * **Recursive Step:** Iterate through `candidates` from the `start` index. * **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]` to `currentCombination`. * Make a recursive call: `backtrack(candidates, remaining - candidates[i], currentCombination, results, i)`. * Remove the last element from `currentCombination` to backtrack. * Call the initial `backtrack` function. * Return `results`. # Solutions ### CSharp ```csharp 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); } } ``` ### Java ```java 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 , 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 ); } } ``` ### CPP ```cpp 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 ; } }; ``` ### Python ```python 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 ans ```