The O(n) Club: Combination Sum — The Java Dev’s Guide to Backtracking Chaos

The O(n) Club: Combination Sum — The Java Dev’s Guide to Backtracking Chaos

⚡ TL;DR

Given a set of numbers, find every unique combo (as many repeats as you want) that hits a target sum. Avoid permutations like the plague. Java makes this easy-ish:

// If you want your CPU to overheat:
void tryAllCombos(int[] arr, int sum) {
    // Try every possible combo, probably spill your coffee
}

🧠 How Devs Usually Mess This Up

Every tired dev (hi, us) mistakes combination for permutation at least once. It’s classic: you print [2,3,2], [3,2,2], [2,2,3]—and then curse when the tester says “uh, they’re the same, Chandler.” Worse, many think you can only use each number once. Nope. Go wild. Stuff [2,2,2,2,2,2] into your list if that hits the target! And if you forget to track your current index in recursion, your backtracking tree turns into an overgrown mutant that eats itself and your output.

🔍 What’s Actually Going On

Imagine you’re building a vending machine menu with infinite coins—pick any coin any number of times to get your snack. Or pretend your meal prep robot is allowed unlimited apples and bananas to reach the calorie goal, but only cares about what’s on the plate, not the order you threw them on. The magic move? Backtracking. Try every choice; if you go bust, rewind fast. Move forward so you don’t trip into duplicates: only ever proceed from the current index or later. Sorting helps; so does not crying when you see the recursion tree.

🛠️ PseudoCode

• Sort the input array. Prune failures way sooner, and pick combos in a consistent order.
• Write a recursive method (dfs/backtrack):
  • Inputs: array, remaining target, start index, combo list, overall results
  • If remaining == 0: add a copy of combo to results (deep copy! Yes, really.)
  • From start through end:
    • If arr[i] > remaining target, break (don’t ask for more fries than you can eat)
    • Add arr[i] to your combo plate
    • Recurse from i again (so you can reuse that number endlessly)
    • Backtrack (remove last item—undo your last snack)

💻 The Code

import java.util.*;
 public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates); // Old-school efficiency
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
     private void backtrack(int[] candidates, int target, int start, List<Integer> combo, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(combo));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) break; // No more oversized combos
            combo.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i, combo, result);
            combo.remove(combo.size() - 1); // Undo the last overeager snack
        }
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Missing deep copy: If you hand the same list instance to every solution, you’ll get a bucket of sadness at the end.
• Not advancing the start index: Welcome to Duplicate City. Population: you.
• No sort? Get ready for slow, wild branching and wasted cycles.
• Duplicates in input? Remove ’em first unless you like bugs.
• Complexity: Large outputs for big targets—blame the combinatorial explosion, not Java.

🧠 Interviewer Brain-Tattoo

If order matters, you’re in permutation land. If you let your recursion wander aimlessly, you’re in bug nation. Keep it sorted, keep it forward, and backtrack with dignity.