The O(n) Club: Combinations (LeetCode 77): Backtracking Your Way Out of Madness

The O(n) Club: Combinations (LeetCode 77) — Backtracking Your Way Out of Madness

⚡ TL;DR

Want every group of k people picked from n? Put down the brute force. Say hello to backtracking: it explores all options, avoids duplicates, and doesn’t make your computer sob. Java cheat-sheet below:

// Returns all combinations of k numbers from 1..n
public List<list>> combine(int n, int k) {
    List<list>> res = new ArrayList<>();
    backtrack(1, n, k, new ArrayList<>(), res);
    return res;
}
private void backtrack(int start, int n, int k, List
<integer> combo, List<list>> res) {
    if (combo.size() == k) {
        res.add(new ArrayList<>(combo));
        return;
    }
    for (int i = start; i <= n; i++) {
        combo.add(i);
        backtrack(i + 1, n, k, combo, res);
        combo.remove(combo.size() - 1);
    }
}
</list></integer></list></list>

🧠 How Devs Usually Mess This Up

Fueled by caffeine, you unleash the double for-loop beast, churning out lovely duplicates like [1,2] & [2,1]. (Surprise! Order doesn’t matter here.) Or worse, you overcomplicate things with Combination Sum logic and infinite recursion party. Common crimes include:

• Mistaking combinations for permutations (no, you do not need both [2,3] and [3,2])
• Skipping the crucial start parameter, so every combo is duplicated like a mischievous mutex loop
• Trying to be greedy (see: infinite loops, repeated elements, and code base tears)

🔍 What’s Actually Going On

Picture forming a team committee: nobody cares if Alice is first and Bob is second. The group is what matters, not their order. That’s why our DFS (depth-first search) only extends a combo with numbers strictly after the last-picked—no duplicate teams, nobody double-booked, and Bob can relax. The magic sauce is that ‘start’ index: always build forward, never backward.

🛠️ PseudoCode

• Start with an empty list res to hold results
• Backtrack function:
  • If combo.length == k, save combo clone to res
  • For i = start to n:
    • Add i to combo
    • Call backtrack with start = i + 1 (the next candidate)
    • Remove last from combo (undo, for new paths)
• Begin recursion with start = 1 and empty combo
• Return res when finished

void backtrack(int start, List<Integer> combo) {
    if (combo.size() == k) {
        res.add(new ArrayList<>(combo));
        return;
    }
    for (int i = start; i <= n; i++) {
        combo.add(i);
        backtrack(i + 1, combo);
        combo.remove(combo.size() - 1);
    }
}

💻 The Code

public class Combinations {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int start, int n, int k, List<Integer> combo, List<List<Integer>> res) {
        if (combo.size() == k) {
            res.add(new ArrayList<>(combo));
            return;
        }
        for (int i = start; i <= n; i++) {
            combo.add(i);
            backtrack(i + 1, n, k, combo, res);
            combo.remove(combo.size() - 1);
        }
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• No start, only pain: Without the start index, expect endless duplicate combos and interviewer facepalms.
• Stack Overflows: If you let i go wild or copy lists by reference, say hi to recursion nightmares or mutation bugs.
• Exponential outputs: With n=20, k=10, results are… a lot. (Seriously, look up “combinatorial explosion” after your TPS reports.)
• Memory Twisters: Each result must be a new list, or you’ll mutate every answer at once (like updating prod on Friday—don’t).
• Complexity: Time and space are stuck at O(C(n,k) * k), because you’re copying each combo of length k. Even Chandler can’t negotiate that down.

🧠 Interviewer Brain-Tattoo

“If you get [1,2] and [2,1], the only thing you’re combining is stress and regret. Start index = sanity.”