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

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.

// Java backtracking skeleton for the impatient
void findCombos(int[] nums, int target) {
    Arrays.sort(nums);
    backtrack(nums, target, 0, new ArrayList<>(), new ArrayList<>());
}

🧠 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

• Sort the array:

  Arrays.sort(candidates);

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

• 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.

• Base case — target met:

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

  Cha-ching! You hit the jackpot.

• Iterate from start to end:

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

• 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.

• 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.

• 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.

💻 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.

🧠 Interviewer Brain-Tattoo

“Sort before you backtrack—because Java’s Arrays.sort() is the closest thing to a bug repellent you’ll ever get.”