Leetcode - 77. Combinations

Problem

Given two integers n and k, return all possible combinations of k numbers chosen from the range 1 to n.

Example

Input: n = 4, k = 2
Output: [
  [1,2],
  [1,3],
  [1,4],
  [2,3],
  [2,4],
  [3,4]
]

---

✨ Approach: Backtracking

The problem is essentially about generating all subsets of size k.
We can solve it using backtracking, which means:

1. Build combinations step by step.
2. At each step, choose a number and recurse to fill the next slot.
3. If the combination reaches length k, add it to the results.
4. Backtrack (remove the last choice) and try the next option.

This ensures we systematically explore all possibilities without duplicates.

---

📌 Key Points

• Use recursion (backtrack(start, comb)) where:

  • start = the next number to consider.
  • comb = current partial combination.

• Use .slice() to push a copy of comb into results, since arrays are mutable.

• Base case: when comb.length === k, save it.

---

🧑‍💻 Code

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    let result = [];

    const backtrack = (start, comb) => {
        // base case: found a full combination
        if (comb.length === k) {
            result.push(comb.slice()); 
            return;
        }

        // explore further choices
        for (let i = start; i <= n; i++) {
            comb.push(i);              // choose
            backtrack(i + 1, comb);    // recurse
            comb.pop();                // undo choice (backtrack)
        }
    };

    backtrack(1, []);
    return result;
};

---

⏱️ Complexity Analysis

• Number of combinations =

$$
C(n, k) = \frac{n!}{k!(n-k)!}
$$

• Time Complexity =

$$
O(C(n, k) \cdot k)
$$

because we generate each combination of length k.

• Space Complexity =

  • Recursion stack: O(k) (depth of recursion).
  • Output: O(C(n, k) * k) (all combinations stored).

---

📝 Summary

• The problem is a classic combinatorial generation.
• Backtracking is the cleanest approach since it explores systematically.
• Using comb.slice() ensures we store independent snapshots of each valid combination.
• Time complexity grows combinatorially, but that’s expected — we must output all combinations anyway.

---

👉 This is the backbone for many similar problems (permutations, subsets, combinations with constraints). Once you grasp this, those feel way easier.

---