The O(n) Club: Combination Sum II — Now With Extra Duplicate Chaos

⚡ TL;DR

Solve for all unique combos in an array (duplicates everywhere!) that add up to a target, using each number no more than once per combo. Never trust a brute force—sort, then backtrack.

🧠 How Devs Usually Mess This Up

So you fire up Eclipse, see duplicates in the array, and think, “Eh, doesn’t matter.” Oops. Watch out for these classics:

Reusing numbers infinitely: Sorry, you’re not in ‘Combination Sum I’-land. Each number is a one-time deal per combo, even if the value repeats.
Printing every permutation: [1,2,5] and [2,1,5] — you can’t fool the interviewer; those are the same groceries, just juggled around.
Skipping only already-picked elements: That’s sweet, but useless for dupes. You need to skip duplicates at the same recursion level after sorting, or you’ll have a relentless déjà vu bug army.

🔍 What’s Actually Going On

Imagine a midnight supermarket sprint. There are two identical loaves of bread, three identical pints of ice cream, and you’re on a mission to reach $50 — exactly. You use each item at most once (no hoarding), but you don’t want to hand the cashier three receipts that all say “bread, ice cream, pasta” in a different order. The fix? Sort first, skip back-to-back duplicates unless they’re fresh picks, and only ever use each index once per combo run. Ban those repeated arrangements like expired coupons.

🛠️ PseudoCode

Classic backtracking:

temp.add(arr[i]);
backtrack(arr, target - arr[i], i + 1, temp, res); // Pass i + 1: no number reuse!
temp.remove(temp.size() - 1);

Build, explore, then unbuild—the Jenga way.

No need to overshoot:

if (arr[i] > target) break;

Because after sorting, if you’re over budget, you’ll just get more over with every new number.

Skip duplicate numbers (at this recursion level):

if (i > start && arr[i] == arr[i-1]) continue;

Translation: If you see the same value twice at this level, act like the second one doesn’t exist.

Iterate from start to end:

for (int i = start; i < arr.length; i++)

Base case — target met:

if (target == 0) res.add(new ArrayList<>(temp));

Cha-ching! You hit the jackpot.

Write a recursive backtrack function:

void backtrack(int[] arr, int target, int start, List<integer> temp, List<list>> res)</list></integer>

‘start’ says: Only consider each number once from each index—no going back in time.

Sort the array:

Arrays.sort(candidates);

Because only sorted twins stand side by side to get skipped properly.

💻 The Code

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

private void backtrack(int[] arr, int target, int start, List<Integer> temp, List<List<Integer>> res) {
    if (target == 0) {
        res.add(new ArrayList<>(temp));
        return;
    }
    for (int i = start; i < arr.length; i++) {
        if (i > start && arr[i] == arr[i-1]) continue;
        if (arr[i] > target) break;
        temp.add(arr[i]);
        backtrack(arr, target - arr[i], i + 1, temp, res);
        temp.remove(temp.size() - 1);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

Missed deduplication: Nuke duplicate combos by always checking i > start && arr[i] == arr[i-1]—otherwise, your recruiter’s going to have déjà vu for hours.
Negative targets: If you keep digging after target < 0, just stop. Sorting lets you bail safely mid-loop.
Results explosion: With lots of unique combos, memory will fill faster than your Slack threads.
Complexity alert: O(2^n) in practice (ish). Anything with backtracking, deduping, and arraylists is here to humble your runtime.