Course4all
Join us on telegram
Home/dsa/Backtracking/Combination Sum

Combination Sum

Master this topic with zero to advance depth.

Combination Sum

The Goal: Finding Target Sum

Given an array of distinct integers candidates and a target integer, find all unique combinations where the chosen numbers sum to target. You may return the combinations in any order.

Key Rule: Unlimited Re-use

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.

Decision Tree Branching

At each step, you can either:

  1. Use the current element: Subtract its value from the target and stay at the same index (because we can re-use it).
  2. Skip the current element: Move to the next index in the array.

Find all unique combinations in candidates that sum to target (reuse allowed). Includes visual decision tree.

Medium

Examples

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

Level I: Basic Backtracking (Include/Exclude)

Intuition

At every step, we either include the current candidate or move to the next candidate.

We use recursion to explore the decision tree. If target == 0, we found a valid combination. If target < 0 or we've used all candidates, we backtrack.

⏱ O(2^T) where T is the target sum.💾 O(T/min_val) for the recursion stack.

Detailed Dry Run

Dry Run: target=7, candidates=[2,3] | Step | idx | target | path | Action | | :--- | :-- | :----- | :------ | :---------------- | | 1 | 0 | 7 | [] | Start | | 2 | 0 | 5 | [2] | Use 2 | | 3 | 0 | 3 | [2,2] | Use 2 | | 4 | 0 | 1 | [2,2,2] | Use 2 | | 5 | 0 | -1 | [2,2,2] | FAIL (Backtrack) | | 6 | 1 | 1 | [2,2] | Skip 2, Try 3 | | 7 | 1 | -2 | [2,2,3] | FAIL (Backtrack) | | 8 | 1 | 7 | [] | Skip all for id=0 |
java
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, target, new ArrayList<>(), candidates, result);
        return result;
    }
    private void backtrack(int idx, int target, List<Integer> current, int[] candidates, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (idx == candidates.length || target < 0) return;
        
        // Use current candidate
        current.add(candidates[idx]);
        backtrack(idx, target - candidates[idx], current, candidates, result);
        current.remove(current.size() - 1);
        
        // Skip current candidate
        backtrack(idx + 1, target, current, candidates, result);
    }
}
Approach 2

Level II: Optimized Backtracking (Loop-Based + Sorting)

Intuition

Sorting the candidates allows us to break early from the loop once the target is exceeded.

For each call, iterate through candidates from the current index to the end. If target - candidates[i] < 0, stop the loop (pruning).

⏱ O(N^(T/M + 1)) where M is the min value.💾 O(T/M)

Detailed Dry Run

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

  1. Try 2. Recurse 5. Try 2. Recurse 3. Try 2. Recurse 1. Try 2 (FAIL - 3rd 2 is fine, 4th fails). Break.
  2. Backtrack to target 3. Try 3. Recurse 0. SUCCESS [2,2,3].
java
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, target, new ArrayList<>(), candidates, result);
        return result;
    }
    private void backtrack(int start, int target, List<Integer> current, int[] candidates, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) break; // Pruning
            current.add(candidates[i]);
            backtrack(i, target - candidates[i], current, candidates, result);
            current.remove(current.size() - 1);
        }
    }
}
Approach 3

Level III: Iterative DP (Unbounded Knapsack Style)

Intuition

Since we only care about the values and can reuse items, we can use a DP table where dp[i] stores all unique combinations summing to i.

Initialize dp[0] with an empty combination. For each candidate, iterate from candidate to target, adding the candidate to all combinations in dp[i - candidate] and storing them in dp[i].

⏱ O(N * T * C) where C is the number of combinations.💾 O(T * C)

Detailed Dry Run

target=3, candidates=[1,2]

  1. dp[0] = [[]], dp[1,2,3] = []
  2. Use 1: dp[1]=[[1]], dp[2]=[[1,1]], dp[3]=[[1,1,1]]
  3. Use 2: dp[2]=[[1,1],[2]], dp[3]=[[1,1,1],[1,2]]
java
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<List<Integer>>> dp = new ArrayList<>();
        for (int i = 0; i <= target; i++) dp.add(new ArrayList<>());
        dp.get(0).add(new ArrayList<>());
        
        for (int c : candidates) {
            for (int i = c; i <= target; i++) {
                for (List<Integer> comb : dp.get(i - c)) {
                    List<Integer> newComb = new ArrayList<>(comb);
                    newComb.add(c);
                    dp.get(i).add(newComb);
                }
            }
        }
        return dp.get(target);
    }
}
← Previous QuestionMaximum Number of Events That Can Be Attended
Next Question →Permutations