Skip to main content
CodePeetCodePeet
CodePeet 150

Combination Sum

MEDIUMProblemSolveExternal Links

Description

You are given an array of distinct positive integers called candidates and a positive integer target. Your task is to find all unique combinations of numbers from candidates where the chosen numbers add up exactly to target.

The key twist: you are allowed to pick the same number as many times as you want. Two combinations are considered different if they use at least one number a different number of times.

Return all such combinations in any order. It is guaranteed that the total number of unique valid combinations will be fewer than 150.

Examples

Example 1

Input: candidates = [2, 3, 6, 7], target = 7

Output: [[2, 2, 3], [7]]

Explanation: There are exactly two ways to reach a sum of 7 using numbers from [2, 3, 6, 7]:

  • Pick 2 twice and 3 once: 2 + 2 + 3 = 7
  • Pick 7 once: 7 = 7

No other combination of these numbers sums to 7. Note that 2 can be reused because unlimited repetition is allowed.

Example 2

Input: candidates = [2, 3, 5], target = 8

Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Explanation: Three combinations sum to 8:

  • 2 + 2 + 2 + 2 = 8 (using 2 four times)
  • 2 + 3 + 3 = 8 (using 2 once and 3 twice)
  • 3 + 5 = 8 (using 3 once and 5 once)

Combinations like [5, 3] are the same as [3, 5] and should not appear twice.

Example 3

Input: candidates = [2], target = 1

Output: []

Explanation: The only candidate is 2, which is already larger than the target 1. No combination of 2s can sum to 1, so the result is an empty list.

Constraints

  • 1 ≤ candidates.length ≤ 30
  • 2 ≤ candidates[i] ≤ 40
  • All elements of candidates are distinct
  • 1 ≤ target ≤ 40

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is to generate every possible combination of candidates (with repetition allowed) and check which ones sum to the target.

Imagine you have a bag of numbered balls. You keep drawing balls (putting each one back after drawing), writing down what you picked, and checking if the total equals the target. If it does, you record that combination. If the total exceeds the target, you stop and try a different path.

This brute-force approach uses recursion to explore all possibilities. At each step, you have a choice for every candidate: include it in the current combination (and keep it available for future picks) or skip it entirely. By trying every possible sequence of picks, you are guaranteed to find all valid combinations.

The critical observation is that to avoid duplicate combinations like [2, 3] and [3, 2], we enforce an ordering rule: once we move past a candidate (decide to skip it), we never go back to it. This ensures each combination is generated exactly once in non-decreasing order.

Step-by-Step Explanation

Let's trace through with candidates = [2, 3, 6, 7], target = 7:

Step 1: Start with an empty combination [], remaining target = 7, starting from index 0 (candidate 2).

Step 2: Pick candidate 2. Combination becomes [2], remaining = 7 - 2 = 5. We can still pick 2 again.

Step 3: Pick candidate 2 again. Combination becomes [2, 2], remaining = 5 - 2 = 3. Still can pick 2.

Step 4: Pick candidate 2 again. Combination becomes [2, 2, 2], remaining = 3 - 2 = 1. Still can pick 2.

Step 5: Pick candidate 2 again. Combination becomes [2, 2, 2, 2], remaining = 1 - 2 = -1. Remaining is negative — this path exceeds the target. Backtrack: remove last 2, go back to [2, 2, 2] with remaining = 1.

Step 6: Skip candidate 2, try candidate 3. Combination = [2, 2, 2], remaining = 1. But 3 > 1, so this path also fails. Try 6 and 7 — both too large. All candidates exhausted. Backtrack to [2, 2] with remaining = 3.

Step 7: Skip candidate 2, try candidate 3. Combination becomes [2, 2, 3], remaining = 3 - 3 = 0. Remaining is exactly 0 — found a valid combination! Record [2, 2, 3]. Backtrack.

Step 8: Continue exploring from [2, 2] — try 6 (too large), try 7 (too large). Backtrack to [2] with remaining = 5.

Step 9: Skip candidate 2, try candidate 3. Combination becomes [2, 3], remaining = 5 - 3 = 2. Try 3 again: [2, 3, 3], remaining = 2 - 3 = -1. Too large. Try 6, 7 — too large. Backtrack to [2, 3] then to [2].

Step 10: Try candidates 6 and 7 from [2]. [2, 6] remaining = -1, too large. [2, 7] remaining = -2, too large. Backtrack to [] with remaining = 7.

Step 11: Skip candidate 2, try candidate 3. Combination = [3], remaining = 4. Pick 3 again: [3, 3], remaining = 1. Pick 3 again: [3, 3, 3], remaining = -2. Too large. Backtrack. Try 6, 7 from [3, 3] — too large. Backtrack to [3] with remaining = 4. Try 6 (too large), try 7 (too large). Backtrack to [].

Step 12: Try candidate 6. [6], remaining = 1. Try 6 again: remaining = -5. Too large. Try 7: too large. Backtrack to [].

Step 13: Try candidate 7. [7], remaining = 7 - 7 = 0. Found a valid combination! Record [7].

Result: [[2, 2, 3], [7]]

Brute Force — Exploring All Candidate Combinations — Watch the recursion tree grow as we try every possible way to pick candidates. Branches are pruned when the remaining target goes negative, and valid leaves are recorded when it hits zero.

Algorithm

  1. Sort the candidates array (optional but helps prune early)
  2. Define a recursive function backtrack(start_index, current_combination, remaining_target):
    • Base case 1: If remaining_target == 0, add current_combination to results
    • Base case 2: If remaining_target < 0, return (overshot)
    • For each candidate from start_index to end:
      • If candidate > remaining_target, break (pruning — all further candidates are too large if sorted)
      • Add candidate to current_combination
      • Recurse with the same start_index (allowing reuse) and reduced remaining_target
      • Remove candidate from current_combination (backtrack)
  3. Return all collected results

Code

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> current;
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0, current, result);
        return result;
    }
    
    void backtrack(vector<int>& candidates, int remaining, int start,
                   vector<int>& current, vector<vector<int>>& result) {
        if (remaining == 0) {
            result.push_back(current);
            return;
        }
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > remaining) break;
            current.push_back(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i, current, result);
            current.pop_back();
        }
    }
};
class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        result = []
        candidates.sort()
        
        def backtrack(start: int, current: list[int], remaining: int):
            if remaining == 0:
                result.append(current[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break
                current.append(candidates[i])
                backtrack(i, current, remaining - candidates[i])
                current.pop()
        
        backtrack(0, [], target)
        return result
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] candidates, int remaining, int start,
                           List<Integer> current, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;
            current.add(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i, current, result);
            current.remove(current.size() - 1);
        }
    }
}

Complexity Analysis

Time Complexity: O(n^(T/M))

Where n is the number of candidates, T is the target value, and M is the smallest candidate value. The recursion tree can be viewed as an n-ary tree where each node has up to n children (one for each candidate). The maximum depth of this tree is T/M because in the worst case we keep adding the smallest candidate until we reach or exceed the target. The total number of nodes is bounded by n^(T/M).

For this problem with candidates up to 30 and target up to 40, this is manageable.

Space Complexity: O(T/M)

The recursion stack can grow as deep as T/M (the maximum length of a valid combination). Additionally, the space to store results depends on the number of valid combinations, which is guaranteed to be less than 150.

Why This Approach Is Not Efficient

The brute-force backtracking approach explores every possible combination path in the recursion tree. While it does prune branches where the remaining target goes negative, it still visits many branches that will ultimately fail.

The fundamental inefficiency is the lack of memory across branches. When exploring different paths, the algorithm doesn't remember results it computed for the same remaining value before. For example, if two different paths both arrive at a state where remaining = 5 and start_index = 1, the algorithm will re-explore the entire subtree from that state both times.

For this particular problem, the constraints are small (target ≤ 40, candidates ≤ 30), so the brute force works. But the concept of eliminating redundant computation leads us to a better approach using dynamic programming or memoization, which systematically builds solutions from smaller subproblems.

Optimal Approach - Backtracking with Sorting and Pruning

Intuition

The optimal approach for this problem is still backtracking — but with a crucial enhancement: sort the candidates first and prune aggressively.

Here's the key insight: if we sort the candidates in ascending order, the moment we encounter a candidate that exceeds the remaining target, we know that all subsequent candidates will also exceed it (since they are even larger). This allows us to immediately break out of the loop instead of checking each remaining candidate one by one.

Think of it like shopping with a budget. If you sort items by price from cheapest to most expensive, and the current item is already too expensive, you don't need to check anything after it — they're all more expensive.

This sorting + pruning strategy dramatically reduces the number of branches explored in practice, especially when the target is small relative to some candidates. Instead of blindly trying every candidate at every level, we stop the moment further exploration is guaranteed to be fruitless.

Additionally, by starting each recursive call at the current candidate index (not re-starting from 0), we inherently avoid generating duplicate combinations. The combination [2, 3] and [3, 2] are the same, and our approach only generates [2, 3] because we never go backward in the candidate list.

Step-by-Step Explanation

Let's trace through with candidates = [2, 3, 6, 7], target = 7 (already sorted):

Step 1: Start: current = [], remaining = 7, index = 0. Candidates in sorted order: [2, 3, 6, 7].

Step 2: Pick 2 → current = [2], remaining = 5. Continue from index 0.

Step 3: Pick 2 → current = [2, 2], remaining = 3. Continue from index 0.

Step 4: Pick 2 → current = [2, 2, 2], remaining = 1. Continue from index 0.

Step 5: Try picking 2 → remaining would be -1 < 0. Since candidates are sorted and 2 > 1, PRUNE: break out of loop. No candidate from index 0 onward can fit. Backtrack to [2, 2] with remaining = 3.

Step 6: Move to index 1 (candidate 3). Pick 3 → current = [2, 2, 3], remaining = 0. FOUND! Record [2, 2, 3].

Step 7: Backtrack to [2, 2]. Move to index 2 (candidate 6). 6 > 3, so PRUNE: break. Backtrack to [2] with remaining = 5.

Step 8: Move to index 1 (candidate 3). Pick 3 → current = [2, 3], remaining = 2. Try 3 again: 3 > 2, PRUNE. Backtrack to [2]. Move to index 2 (candidate 6): 6 > 5, PRUNE. Backtrack to [] with remaining = 7.

Step 9: Move to index 1 (candidate 3). Pick 3 → current = [3], remaining = 4. Pick 3 → [3, 3], remaining = 1. Try 3: 3 > 1, PRUNE. Backtrack to [3]. Try 6: 6 > 4, PRUNE. Backtrack to [].

Step 10: Move to index 2 (candidate 6). Pick 6 → current = [6], remaining = 1. Try 6: 6 > 1, PRUNE. Backtrack to [].

Step 11: Move to index 3 (candidate 7). Pick 7 → current = [7], remaining = 0. FOUND! Record [7].

Step 12: All candidates exhausted from root. Return [[2, 2, 3], [7]].

Optimal Backtracking — Sort + Prune Exploration — Watch how sorting candidates and breaking early eliminates entire subtrees. Pruned branches (red) show where sorting saved us from unnecessary exploration.

Algorithm

  1. Sort the candidates array in ascending order
  2. Define a recursive function backtrack(start, current, remaining):
    • If remaining == 0, record current as a valid combination
    • For each candidate from index start to the end:
      • If candidate > remaining, break (sorted order guarantees all further candidates also exceed remaining)
      • Add candidate to current
      • Recurse with the same index (allows reuse) and remaining - candidate
      • Remove candidate from current (backtrack)
  3. Call backtrack(0, [], target) and return all collected combinations

Code

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> current;
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0, current, result);
        return result;
    }
    
    void backtrack(vector<int>& candidates, int remaining, int start,
                   vector<int>& current, vector<vector<int>>& result) {
        if (remaining == 0) {
            result.push_back(current);
            return;
        }
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > remaining) break; // Pruning: sorted order
            current.push_back(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i, current, result);
            current.pop_back(); // Backtrack
        }
    }
};
class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        result = []
        candidates.sort()
        
        def backtrack(start: int, current: list[int], remaining: int) -> None:
            if remaining == 0:
                result.append(current[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break  # Pruning: sorted order
                current.append(candidates[i])
                backtrack(i, current, remaining - candidates[i])
                current.pop()  # Backtrack
        
        backtrack(0, [], target)
        return result
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] candidates, int remaining, int start,
                           List<Integer> current, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break; // Pruning: sorted order
            current.add(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i, current, result);
            current.remove(current.size() - 1); // Backtrack
        }
    }
}

Complexity Analysis

Time Complexity: O(n^(T/M))

In the worst case, the complexity remains O(n^(T/M)) where n is the number of candidates, T is the target, and M is the smallest candidate. However, in practice, sorting + pruning eliminates large portions of the search tree. When a candidate exceeds the remaining target, we skip it AND all larger candidates in one break statement. This makes the average case significantly faster.

For the given constraints (n ≤ 30, target ≤ 40, min candidate ≥ 2), the maximum tree depth is 20 (40/2), and pruning keeps the actual exploration well within time limits.

Space Complexity: O(T/M)

The recursion stack depth is at most T/M (the longest possible combination uses the smallest candidate repeatedly). Each stack frame uses O(1) extra space. The result storage is separate and bounded by the number of valid combinations (guaranteed < 150).