Leetcode 77: Combinations

 

1. Problem Statement (Simple Explanation)

You’re given two integers n and k.

You must return all possible combinations of k numbers chosen from the range [1, n] (inclusive).

• Each combination is a set of k distinct numbers.

• Combinations are unordered:

• [1,2] and [2,1] are the same combination; you should only output one of them.

• You can return the combinations in any order.

2. Examples

Example 1:

Input: n = 4, k = 2

All 2-number combinations from {1,2,3,4}:

• [1,2]

• [1,3]

• [1,4]

• [2,3]

• [2,4]

• [3,4]

Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Example 2:

Input: n = 1, k = 1

Only one combination: [1].

Output: [[1]]

3. Approach – Backtracking (DFS)

We need to generate all subsets of size k from numbers 1..n.

Natural approach: backtracking (depth-first search):

• Maintain:

• current list = current combination being built.

• start = next number to consider.

At each step:

• If current.size() == k:

• We have a complete combination → add a copy to the result.

• Else:

• For each i from start to n:

• Add i to current.

• Recurse with start = i + 1 (to avoid reusing smaller numbers and preserve order).

• Remove i from current (backtrack).

Pruning Optimization:

If we know there are not enough numbers left to fill the remaining slots, we can stop early:

• Suppose we need (k - current.size()) more numbers.

• The highest starting i we should try is:

i <= n - (k - current.size()) + 1

This avoids unnecessary recursion.

Pseudo-code:

Complexity:

Let C = C(n, k) = number of combinations.

• Time:

• We generate each combination once: O(C).

• Each combination construction costs O(k) to copy.

• Overall roughly O(C * k).

• Space:

• current stack up to size k: O(k).

• Result stores O(C * k) output (which is required).

n <= 20, so this is easily manageable.

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code