The O(n) Club: Combination Sum III, or: Picking K Numbers that Add Up, But Skip the Guilt

The O(n) Club: Combination Sum III, or: Picking K Numbers that Add Up, But Skip the Guilt

⚡ TL;DR

Find every possible set of k unique numbers (1-9) that add up to n. Each number shows up once, and if you try to sneak in a duplicate like it’s free pizza at a startup, you’ll fail the interview. Try every path, prune with extreme prejudice, and always leave room for dessert (or early returns).

public List<List<Integer>> comboSum3(int k, int n) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(1, k, n, new ArrayList<>(), res);
    return res;
}

🧠 How Devs Usually Mess This Up

They treat it like any other Combination Sum problem, letting numbers repeat until the combo list looks like a club sandwich. Or they don’t check the sum and count together—ending up with combos like [2,3,4,5] when k = 3. Hint: If your output has twins or the count is off, you missed the point. Also, don’t sort after the fact—generate in ascending order so duplicates never even get invited.

🔍 What’s Actually Going On

You’re hosting a very exclusive party: only numbers 1–9 are eligible, and each one gets exactly one drink ticket. You need to assemble exactly k guests whose combined drink count (sum) matches n. Anyone over-imbibing or sneaking in extra guests gets bounced, fast. Backtracking lets you try every possible guest list, but you should close the door the moment the room is too packed or you’ve run out of punch (n goes negative or combo gets too long).

🛠️ PseudoCode

• Start with an empty list (your cool party), sum=n, index=1, k guests to fill.
• For each number i from current index to 9:
  • Add i to the party.
  • Recurse to fill the rest: index becomes i+1, k stays the same, n drops by i.
  • If sum < 0 or party too crowded (size > k): back out, fire the bouncer (remove i).
  • If sum==0 and party size == k: take a picture (add list to results).
  • Rinse, repeat, and always clean up (remove last number after each attempt).

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

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• No number repeats: If you’re recreating [1,1,5], start over (and read the problem again).
• Skip unnecessary paths: If n drops below zero or combo overflows size k, abort mission—no miracle save is coming.
• Combos in weird order or duplicates: Always increase start; otherwise, different orderings of the same group sneak in.
• Hopeless inputs: Want 4 numbers adding up to 3? Return nothing and declare an early lunch.
• Pretend it’s huge: Inputs are small (1–9), so brute force won’t burn the data center, but pruning stops your laptop fan from taking flight.
• Space Notes: At most O(k) in stack per branch—no threat to your JVM or office power grid.

🧠 Interviewer Brain-Tattoo

“Always kick out party crashers early—prune as soon as your combo is too big or the sum’s blown, and let backtracking do the guest list magic.”