Q21: How do you solve Combination Sum (reusing numbers to hit target sum)?

Find all unique combinations of candidates that sum to target. candidates can be chosen unlimited times. Recursively subtract candidate from target. If target == 0, add snapshot to result. If target < 0, return. Pass i (not i + 1) to recursive call to allow element reuse.

Combination Sum Backtracking

import java.util.*;

public class CombinationSum {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }
    private static void backtrack(List<List<Integer>> result, List<Integer> temp, int[] candidates, int remain, int start) {
        if (remain < 0) return;
        if (remain == 0) { result.add(new ArrayList<>(temp)); return; }
        for (int i = start; i < candidates.length; i++) {
            temp.add(candidates[i]);
            backtrack(result, temp, candidates, remain - candidates[i], i); // i permits reuse
            temp.remove(temp.size() - 1);
        }
    }
}

💡 Reuses current candidate elements by passing index i recursively.

Key Takeaways

Allowing element reuse requires calling backtrack(i) instead of i + 1.
Prune recursion branches when target becomes negative.

Knowledge Check

What parameter controls whether candidate elements can be reused multiple times during backtracking?

Q21: How do you solve Combination Sum (reusing numbers to hit target sum)?

STAY UPDATED WITH BYTES!