Combination Sum Variants

Combination Sum I (LeetCode 39)

Target sum using candidate numbers that can be reused an unlimited number of times.

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(candidates); // Sort for optimization
    backtrack(candidates, target, 0, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] cands, int target, int start, int currentSum, 
                         List<Integer> path, List<List<Integer>> res) {
    if (currentSum == target) {
        res.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = start; i < cands.length; i++) {
        // Optimization: because candidates are sorted, if current sum + next candidate 
        // exceeds target, all subsequent candidates in the loop will also exceed it.
        if (currentSum + cands[i] > target) break; 
        
        path.add(cands[i]);
        // Pass 'i' instead of 'i+1' to the recursive call to allow re-using the same element
        backtrack(cands, target, i, currentSum + cands[i], path, res);
        path.removeLast();
    }
}

Combination Sum II (LeetCode 40)

Numbers in candidates may be used only once, and candidates may contain duplicates.

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(candidates, target, 0, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] cands, int target, int start, int currentSum, 
                         List<Integer> path, List<List<Integer>> res) {
    if (currentSum == target) {
        res.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = start; i < cands.length; i++) {
        if (currentSum + cands[i] > target) break;
        
        // Skip horizontal duplicates: if this branch's candidate is the same as the previous 
        // sibling's, skip it to avoid generating the same combination twice.
        if (i > start && cands[i] == cands[i - 1]) continue;
        
        path.add(cands[i]);
        // Pass 'i + 1' to move to the next unique candidate
        backtrack(cands, target, i + 1, currentSum + cands[i], path, res);
        path.removeLast();
    }
}

Combination Sum III (LeetCode 216)

Find all possible combinations of $k$ numbers that sum to $n$, using only digits 1 through 9.

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(k, n, 1, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int k, int n, int start, int currentSum, 
                         List<Integer> path, List<List<Integer>> res) {
    if (path.size() == k) {
        if (currentSum == n) res.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = start; i <= 9; i++) {
        if (currentSum + i > n) break; // Optimization
        path.add(i);
        backtrack(k, n, i + 1, currentSum + i, path, res);
        path.removeLast();
    }
}

Target Sum (LeetCode 494)

Assign $+$ or $-$ signs to every integer in an array to reach a target.

Backtracking Approach (Conceptual)

public int findTargetSumWays(int[] nums, int target) {
    return dfs(nums, target, 0, 0);
}

private int dfs(int[] nums, int target, int index, int currentSum) {
    if (index == nums.length) return currentSum == target ? 1 : 0;
    return dfs(nums, target, index + 1, currentSum + nums[index])
         + dfs(nums, target, index + 1, currentSum - nums[index]);
}

Optimizing with Dynamic Programming (0-1 Knapsack)

We can divide nums into two sets: $P$ (positive numbers) and $N$ (negative numbers).

• $sum(P) - sum(N) = target$
• $sum(P) + sum(N) = sum(total)$
• Result: $sum(P) = (target + total) / 2$

This reduces the problem to finding subsets that sum to $(target + total) / 2$.

public int findTargetSumWays(int[] nums, int target) {
    int total = 0;
    for (int n : nums) total += n;
    
    if (Math.abs(target) > total || (target + total) % 2 != 0) return 0;
    int bagSize = (target + total) / 2;
    
    int[] dp = new int[bagSize + 1];
    dp[0] = 1;
    for (int x : nums) {
        for (int j = bagSize; j >= x; j--) dp[j] += dp[j - x];
    }
    return dp[bagSize];
}

Pattern Comparison Table