08.CombinationSumII.md

Combination Sum II 🧩✨

Problem statement 📝

• Input: candidates — array of positive integers (may contain duplicates), and an integer target.
• Output: All unique combinations of numbers from candidates where the chosen numbers sum to target.
• Constraint: Each element in candidates may be used once in a combination.
• Order of combinations in the output does not matter, but each distinct combination (as a multiset) must appear exactly once.

Example:

candidates = [10,1,2,7,6,1,5], target = 8

One valid output:
[
  [1,1,6],
  [1,2,5],
  [1,7],
  [2,6]
]

Intuition ✨

This is a backtracking / DFS problem with two complications:

1. Each candidate may be chosen at most once → when you recurse after choosing arr[i], you start the next recursion at i+1.
2. Candidates contain duplicates, and you must avoid generating duplicate combination results. Sorting the array first groups equal values together — then, during the loop you skip a candidate if it’s the same as the previous candidate at the same recursive level (if (i > ind && arr[i] == arr[i-1]) continue;). That ensures each distinct combination is generated exactly once.

Pruning: Because the array is sorted, when arr[i] > target you can break the loop early — all further elements are ≥ arr[i].

---

Brute-force idea (why naive is bad) 🐢

A brute-force approach would try all subsets of candidates (there are 2^n of them) and check which ones sum to target, then deduplicate results. That’s inefficient — generating duplicates and doing heavy post-processing.

The sorted+pruned backtracking approach avoids generating invalid or duplicate combinations in the first place.

Algorithm (backtracking with pruning & duplicate skip) ✅

1. Sort candidates ascending.

2. Start DFS/backtracking from index 0 with an empty combination ds and remaining target.

3. At recursion level with starting index ind:

   • If target == 0, push ds into results.

   • Loop i from ind to arr.size()-1:

     • Skip duplicates at the same level: if i > ind and arr[i] == arr[i-1], continue.
     • Prune by value: if arr[i] > target, break.
     • Choose arr[i]: push it to ds, recurse with i+1 (not i) and target - arr[i].
     • Backtrack: pop the last element.

4. Return results.

This ensures:

• Each index is used at most once per path (because recursion moves to i+1).
• Duplicate candidate values only produce combinations where the first occurrence in the group is considered at a given level — duplicates are skipped when they would otherwise replicate the same multiset.

Full code 🧾

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        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 (target == 0) {
            res.push_back(ds);
            return;
        }

        for (int i = ind; i < arr.size(); i++) {
            if (i > ind && arr[i] == arr[i-1])
                continue;
            if (arr[i] > target) 
                break;
            
            ds.push_back(arr[i]);
            combination(i + 1, arr, target - arr[i], ds, res);
            ds.pop_back();
        }
    }
};

Worked example — step by step 🔍

Input: candidates = [2,5,2,1,2], target = 5

1. Sort → [1,2,2,2,5].

2. Start ind=0, target=5, ds=[]:

   • i=0 choose 1 → ds=[1], recurse ind=1, target=4.

     • i=1 choose 2 → ds=[1,2], recurse ind=2, target=2.

       • i=2 choose 2 → ds=[1,2,2], recurse ind=3, target=0 → push [1,2,2]
       • backtrack
       • i=3 skip because arr[3]==arr[2] and i>ind

     • backtrack

     • i=2 skip duplicate at same level (since i>ind and arr[2]==arr[1])

     • ...

   • i=1 choose 2 → ds=[2], recurse ind=2, target=3.

     • i=2 choose 2 → ds=[2,2], recurse ind=3, target=1.

       • i=3 2 > target break

     • i=3 skip duplicate

   • i=4 choose 5 → ds=[5], recurse ind=5, target=0 → push [5]

Output: [[1,2,2],[5]].

Note duplicates like [2,1,2] are not produced because of ordering and duplicate skip — combinations are generated in non-decreasing order.

Complexity analysis 📊

• Time complexity: Exponential in worst case — generating all unique combinations can be large. A loose bound is O(2^n) in the worst case, but effective runtime is much smaller due to pruning (arr[i] > target) and skipping duplicates. For typical constraints (LeetCode-like), backtracking is acceptable.

• Space complexity:

  • Recursive call stack depth ≤ n (number of candidates) → O(n).
  • Auxiliary space for current combination ds is O(n) and for results depends on number and size of found combinations (could be large).
  • Sorting costs O(n log n) time and O(1) or O(n) extra space depending on sort implementation.

---

Test cases 🧪

1. Example with duplicates

   • candidates=[10,1,2,7,6,1,5], target=8 Expected output: [[1,1,6],[1,2,5],[1,7],[2,6]] (order may vary)

2. Multiple duplicates

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

3. Single candidate

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

4. No solution

   • candidates=[3,4], target=2 → []

5. All candidates larger than target

   • candidates=[9,10], target=8 → [] (quick arr[i] > target break)

6. Empty candidates

   • candidates=[], target=0 → [] or [[]] depending on interpretation — this code returns [] (no push unless target==0 at recursion start; if you want [[]] for target==0 you can handle explicitly).

Implementation details & important observations ✅

• Sorting is mandatory for the duplicate-skip logic to work correctly.
• Duplicate skip rule: if (i > ind && arr[i] == arr[i-1]) continue; — this only skips duplicates at the same recursive level. It allows repeated use of the same value at deeper levels when appropriate (but still uses each individual element at most once by advancing the index).
• i + 1 recursion ensures each element is used at most once per combination.
• Pruning early: if (arr[i] > target) break; — thanks to sorting, you can stop the loop early when elements exceed the remaining target.

Tips & best practices ✨

• Use sort(candidates.begin(), candidates.end()) — required.

• Pass candidates by reference (the code does that).

• If input size is moderate, this straightforward approach is fine. For large inputs:

  • Consider small optimizations like reserving vector capacity for ds.
  • If you only need a count of combinations (not the combinations themselves), switch to DP.

• Keep combinations in non-decreasing order to make duplicate elimination trivial.

• When writing tests, include duplicate-heavy inputs and edge cases (empty array, small/large targets).

Variations & extensions 🔁

• Combination Sum I (unlimited use): Similar but you call recursion with i (stay at same index) when choosing a number (allow repeats).
• Combination Sum III: fixed combination size k and numbers 1..9, choose exactly k numbers summing to n.
• Subset Sum / 0-1 Knapsack: when you only need to know if a subset exists (decision problem) or maximum sum under capacity, dynamic programming is appropriate.
• Allow duplicates across input meaningfully: if input has duplicates but elements are considered distinct (by index), remove the duplicate-skip line; this variant is less common.

Frequently Asked Questions (FAQ) ❓

Q: Why sort the array?

A: Sorting groups duplicates and enables both the duplicate-skip rule and the early break (arr[i] > target) pruning.

Q: How does the duplicate skip i > ind && arr[i] == arr[i-1] work?

A: At a given recursion level (fixed ind), this avoids trying the same value more than once as the first choice at that level. It prevents generating identical combinations that differ only by which duplicate instance was chosen.

Q: Does this algorithm generate combinations in any particular order?

A: Yes — combinations are generated in non-decreasing order (relative to the sorted candidates) because we only move forward in the array. But the overall list order is determined by recursion traversal and not strictly lexicographic unless you enforce it.

Q: Can the same number appear multiple times in a combination?

A: Only if it appears multiple times in candidates. Each element in candidates is used at most once; duplicates in input allow repeated values in a combination but as separate elements. This is the core difference between Combination Sum (I) (unlimited use) and Combination Sum II (single use).

Q: Will this approach miss combinations?

A: No — provided you sorted the array. The approach explores all combinations that respect the "use each index at most once" rule, and the duplicate skipping only avoids duplicate multisets, not unique ones.

Q: Complexity concerns?

A: The algorithm is exponential in the worst case (unavoidable for enumerating all combinations). Sorting costs O(n log n) extra time.