14.3 Combination Sum

14.3.1 Problem Metadata

14.3.2 Description

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.

14.3.3 Examples

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: []

14.3.4 Constraints

  • \(1 \le \text{candidates.length} \le 30\)
  • \(2 \le \text{candidates}[i] \le 40\)
  • All elements of candidates are distinct
  • \(1 \le \text{target} \le 40\)

14.3.5 Solution - Dynamic Programming (Unbounded Knapsack)

14.3.5.1 Walkthrough

This problem is a classic Unbounded Knapsack variant where each candidate can be used unlimited times to reach the target sum.

Core Strategy:

Build up solutions from smaller sums to the target. Use a DP table where dp[i] stores all combinations that sum to i. For each amount from 1 to target, try adding each candidate and extend the combinations from dp[amount - candidate].

Key Insight - Avoiding Duplicates:

To prevent duplicate combinations like [2,3] and [3,2], only add a candidate if it maintains non-decreasing order. Check if the candidate is greater than or equal to the last element in the existing combination.

Step-by-step execution for candidates = [2,3,6,7], target = 7:

dp[0] = [[]]           (empty combination sums to 0)
dp[1] = []             (no candidates $\le$ 1)
dp[2] = [[2]]          (from dp[0] + 2)
dp[3] = [[3]]          (from dp[0] + 3)
dp[4] = [[2,2]]        (from dp[2] + 2, since 2 $\ge$ 2)
dp[5] = [[2,3]]        (from dp[2] + 3, since 3 $\ge$ 2)
dp[6] = [[2,2,2], [6]] (from dp[4] + 2 and dp[0] + 6)
dp[7] = [[2,2,3], [7]] (from dp[4] + 3 and dp[0] + 7)

The answer is dp[7] = [[2,2,3], [7]].

Why Non-Decreasing Order Works:

  • Forces a canonical ordering: [2,2,3] exists but [2,3,2] and [3,2,2] are never generated
  • Only extends a combination if new candidate \(\ge\) last element
  • Guarantees uniqueness without needing a Set or post-processing

14.3.5.2 Analysis

  • Time Complexity: O(target × n × k)
    • Outer loop: O(target) iterations for each amount
    • Middle loop: O(n) candidates to try
    • Inner loop: O(k) where k is the average number of combinations per amount
    • In worst case, k can be exponential, but bounded by problem constraint (< 150 combinations)
  • Space Complexity: O(target × k)
    • DP array has (target + 1) entries
    • Each entry stores up to k combinations
    • Each combination stores up to (target / min_candidate) elements

14.3.5.3 Implementation Steps

Initialization: 1. Create array dp of size (target + 1) where each entry is a list of combinations 2. Initialize dp[0] = [[]] (base case: empty combination sums to 0)

DP Table Construction: 3. For each amount from 1 to target: 1. For each candidate in candidates array: - Skip if candidate \(>\) amount (cannot use it) - Calculate remaining = amount - candidate - For each combination in dp[remaining]: - Check if we can add candidate (maintains non-decreasing order) - If combination is empty OR candidate \(\ge\) last element in combination: - Create new combination by copying existing and appending candidate - Add to dp[amount]

Return Result: 4. Return dp[target] (all combinations that sum to target)

14.3.5.4 Code - Java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    // dp[i] = list of all combinations that sum to i
    List<List<Integer>>[] dp = new ArrayList[target + 1];

    // Initialize
    for (int i = 0; i <= target; i++) {
        dp[i] = new ArrayList<>();
    }

    // Base case
    dp[0].add(new ArrayList<>());
    
    for (int i = 1; i <= target; i++) {
        //for each candidate c
        for (int c : candidates) {
            // skip if candidate is too big, c > i
            if (c <= i) {
                //for each combination in dp[remaining]
                for (List<Integer> combo : dp[i - c]) {
                    if (combo.isEmpty() || c >= combo.get(combo.size() - 1)) {
                        //create new combination by 1. cloning 2. appending candidate in increasing order
                        List<Integer> newCombo = new ArrayList<>(combo);
                        newCombo.add(c);
                        dp[i].add(newCombo);
                    }
                }
            }
        }
    }

    return dp[target];
}

14.3.5.5 Code - Golang

func combinationSum(candidates []int, target int) [][]int {
    // dp[i] = list of all combinations that sum to i
    dp := make([][][]int, target + 1);

    for i := 0; i <= target; i++ {
        dp[i] = make([][]int, 0)
    }

    dp[0] = append(dp[0], make([]int, 0))

    for i := 1; i<= target; i++ {
        //for each candidate c
        for _, c := range(candidates) {
            // skip if candidate is too big, c > i
            if c <= i { 
                //for each combination in dp[remaining]
                for _, combo := range(dp[i-c]) {
                    if len(combo) == 0 || c >= combo[len(combo) - 1] {
                        //create new combination by 1. cloning 2. appending candidate in increasing order
                        newCombo := append([]int{}, combo...)                    
                        newCombo = append(newCombo, c)
                        dp[i] = append(dp[i], newCombo)
                    }
                }
            }
        }
    }

    return dp[target];
}