07.CombinationSum.md

Combination Sum 🔎➕🍃

Problem statement 📝

Given a set of distinct positive integers candidates and a target integer target, return a list of all unique combinations of candidates where the numbers sum to target. Each candidate may be chosen an unlimited number of times. Combinations may be returned in any order.

Example:

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

Intuition ✨

This is a classic combinational generation / unbounded knapsack style problem. Think recursively:

• For each index i (candidate arr[i]) you have two choices:

  • Pick it: subtract arr[i] from target, keep index i (because reuse allowed), and recurse.
  • Skip it: move to index i+1 (don’t use arr[i] anymore) and recurse.

Stop when you either hit target == 0 (record solution) or run out of candidates / go negative (stop path).

Two useful optimizations:

1. Sort candidates ascending and prune when arr[i] > target (early stop).
2. Pass arrays by const reference to avoid copying candidate arrays at each recursion call (big win).

Brute force idea (why naive is bad) 🐢

You could try every possible multiset by exploring counts for each candidate, but this brute force enumerates a huge number of combinations and repeats many impossible partial sums. Backtracking with pruning generates only feasible partial combinations and avoids wasted work.

Correct Approach (backtracking) ✅

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> ds;

        combination(0, candidates, target, ds, res);
        return res;
    }

    void combination(int ind, vector<int> arr, int target, vector<int> &ds, vector<vector<int>> &res) {
        if (ind == arr.size()) {
            if (target == 0) {
                res.push_back(ds);
            }
            return;
        }

        if (arr[ind] <= target) {
            ds.push_back(arr[ind]);
            combination(ind, arr, target - arr[ind], ds, res);
            ds.pop_back();
        }

        combination(ind + 1, arr, target, ds, res);
}

Example run (walkthrough)

candidates = [2,3,6,7], target = 7 (after sorting: same)

• Start: ind=0, target=7, ds=[].

• Try take 2: ds=[2], target=5, stay ind=0.

  • take 2: ds=[2,2], target=3, stay ind=0.

    • take 2: target=1 → can't (2 > 1), skip to next candidate.
    • skip to 3: take 3 → target=0 → record [2,2,3].

  • backtrack...

• Skip all 2s and eventually try 7 and record [7].

Results: [[2,2,3], [7]].

Complexity analysis 📊

Let k be the number of candidates and target be T.

• Time complexity: The worst-case time is exponential. A loose upper bound is O(k * (T/min_cand)^{depth}) but more practically the number of valid combinations is bounded by the compositions of T with parts from candidates, which is exponential in T / min(candidates). A common analysis: number of possible combinations ≈ O((T/minCand)^(k)) in worst cases; each combination takes up to O(T / minCand) time to build/copy. So exponential time.

• Space complexity:

  • Recursion depth at most T / minCandidate (if we keep picking min value), so O(T / minCand) stack + O(n) for each output combination stored. Output size can be large (exponential), so space complexity including output is O(#solutions * average_solution_length).

In short: exponential time & space in worst case (as unavoidable for enumerating all solutions).

---

Test cases ✅

Use a mix of simple, edge, and tricky tests.

1. Example

   • candidates = [2,3,6,7], target = 7 Expected: [[7], [2,2,3]] (order may vary)

2. Single candidate

   • candidates = [2], target = 8 Expected: [[2,2,2,2]]

3. No solution

   • candidates = [5,3], target = 1 → []

4. Multiple ways, reused candidates

   • candidates = [2,3,5], target = 8 Expected (one valid set): [3,5], [2,2,2,2], [2,3,3], etc.

5. Candidates unsorted input

   • candidates = [7,2,3], target = 7 Sorting should still give correct [7] and [2,2,3].

6. Edge cases

   • candidates = [], target = 7 → []
   • target = 0 → usually [] or [[]] depending on problem spec. For LeetCode target >= 1 typically; you can define: if target==0 return {} or { { } } — decide consistently.

Tips & tricks ✨

• Sort the candidates first. Sorting lets you prune: when arr[ind] > target, you can stop exploring further indices because they are ≥ arr[ind].
• Pass by const reference: const vector<int>& arr.
• Reserve vector capacity for ds (optional): ds.reserve(target / arr[0] + 1) to reduce reallocations.
• Use iterative deepening or memoization if you only need count of combinations (not list).
• If you need combinations in a canonical order, sorting candidates and choosing them in order yields lexicographically ordered sequences (by candidate order).
• Avoid duplicates: The approach above only allows non-decreasing combinations (because we either stay at ind when taking or move to ind+1 when skipping) so each unique multiset appears once; no extra dedup logic required.

Variations & extensions 🔁

• Combination Sum II: each candidate may be used only once, and input may contain duplicates. You must sort and skip duplicates by checking if (i>start && candidates[i]==candidates[i-1]) continue;.
• Count combinations only: Use DP (coin-change style) to compute counts (polynomial time).
• Bounded repetition: each candidate has limited count — adapt recursion to loop over take_count = 0 .. max_allowed for each index.
• Return combinations with fixed length: Add a constraint on combination size and prune accordingly.

Frequently Asked Questions (FAQs) ❓

Q: Why do we not need to de-duplicate results?

A: Because we enforce a choice ordering (take keeps index the same, skip increments index). This generates combinations in non-decreasing order of candidate indices, so the same multiset cannot be generated twice.

Q: Can candidates contain duplicates?

A: The classic problem assumes distinct candidates. If duplicates exist in input, sort and remove duplicates before backtracking or handle skip-duplicate logic (as in Combination Sum II).

Q: Why sort?

A: Sorting allows early pruning: if arr[ind] > target, you can skip trying any later candidates at this level. It also provides deterministic ordering.

Q: Can we optimize with DP / memoization?

A: If you only need the count of solutions, dynamic programming is ideal. If you need actual combinations, memoization can help prune repeated subproblems but storing solution lists for subtargets can be heavy.

Q: Is recursion depth a problem?

A: Depth equals maximum number of times you can pick the smallest candidate (target / minCandidate). For very large targets relative to smallest candidate, this can be deep. Convert to iterative or increase recursion limits if necessary.