Combinations (LC 77)

Pattern: Backtracking
Difficulty: Medium
Key Concept: Choose exactly k distinct numbers from 1..n without caring about order — build increasing sequences and prune when too few numbers remain.

Problem Statement

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

Input

• n: positive integer — usable values are 1, 2, …, n.
• k: 0 <= k <= n — size of each combination.

Output

• List<List<Integer>> — each inner list has length k; standard DFS produces combinations in increasing order.

Example

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

---

1. Algorithm & Pseudocode

Brute force

result = empty
for each subset of {1..n}:
    if subset.size() == k:
        result.add(subset)
return result

Optimal — backtracking + pruning

result = empty
current = empty

backtrack(start):
    if current.size() == k:
        result.add(copy of current)
        return
    need = k - current.size()
    for i from start to n:
        if (n - i + 1) < need:
            break          // not enough numbers left from i..n
        current.add(i)
        backtrack(i + 1)
        current.remove last

Equivalent tight loop: for (int i = start; i <= n - need + 1; i++) — same bound, fewer iterations than 1..n without check.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why increasing picks? [1,2] and [2,1] are the same combination. Always choosing the next number greater than the last (backtrack(i + 1)) counts each subset once.

2. Brute force over all subsets — There are 2^n subsets. Filtering to size k is correct but wasteful; depth-limited backtracking stops at height k.

3. Why prune? If you still need need numbers but only n - i + 1 values remain from i to n, you cannot finish. Skipping those i values avoids empty recursive work.

4. Formula i <= n - need + 1 — You need need distinct integers from {i, i+1, …, n}. That interval has length n - i + 1. Require n - i + 1 >= need ⇒ i <= n - need + 1.

5. ArrayList.size() is O(1) in Java — safe to use cur.size() inside the bound.

---

3. The Dry Run

Sample: n = 4, k = 2.

Before each loop: need = k - cur.size(). Max valid i is n - need + 1.

Call #	cur	start	need	max i	Choices for i	Notes
1	[]	1	2	4-2+1=3	1, 2, 3	Never start at 4 alone — cannot pick a second number
2	[1]	2	1	4-1+1=4	2, 3, 4	Yields [1,2],[1,3],[1,4]
3	[2]	3	1	4	3, 4	Yields [2,3],[2,4]
4	[3]	4	1	4	4	Yields [3,4]

DFS order trace (first few returns)

Step	Action	cur after
1	add 1, add 2	[1,2] → save → pop → [1]
2	try 3	[1,3] → save → pop → [1]
3	try 4	[1,4] → save → pop → []
4	pop 1 implied, add 2 at root level	[2] → …

Final list (typical order): [1,2], [1,3], [1,4], [2,3], [2,4], [3,4].

---

4. Java Solution

Brute Force

Enumerate all subsets of {1..n} with bitmask or include/exclude recursion; keep those of size k.

Time: O(2^n · k)
Space: O(k) auxiliary + output

import java.util.*;

class SolutionBrute {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> all = new ArrayList<>();
        backtrackAll(1, n, new ArrayList<>(), all);
        List<List<Integer>> result = new ArrayList<>();
        for (List<Integer> s : all) {
            if (s.size() == k) result.add(s);
        }
        return result;
    }

    private void backtrackAll(int start, int n, List<Integer> cur, List<List<Integer>> all) {
        if (start > n) {
            all.add(new ArrayList<>(cur));
            return;
        }
        cur.add(start);
        backtrackAll(start + 1, n, cur, all);
        cur.remove(cur.size() - 1);
        backtrackAll(start + 1, n, cur, all);
    }
}

Optimal

import java.util.*;

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>(), result);
        return result;
    }

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

---

5. The “Java vs. Others” Edge

• Pruning i <= n - (k - cur.size()) + 1 — same idea in C++. In Python, mind off-by-one: range(start, n - need + 2) because range excludes the high end.
• Without pruning — recursion depth is still k, but you explore dead branches (e.g. starting with n when k = 2 and n = 4). Pruning removes those calls at the loop level.
• ArrayList — add / remove(size-1) mirror stack push/pop for the current combination.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(2^n · k)	O(k) + output	Visits all subsets
Optimal	O(C(n,k) · k)	O(k) stack + output	C(n,k) leaves; k work per copy

C(n,k) = n! / (k!(n-k)!).