Combinations

Explanation & Solution

Practice Problem

Description

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

You may return the answer in any order.

Input: n = 4, k = 2

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

Explanation: There are C(4,2) = 6 ways to choose 2 numbers from [1,2,3,4]. Note that combinations are unordered, so [1,2] and [2,1] are considered the same.

Constraints

1 <= n <= 20
1 <= k <= n

Approach

Subsets pattern

1. Backtracking Setup

Initialize an empty result array to collect all valid combinations
Define a recursive backtrack(start, current) function
start is the smallest number we can still pick (ensures ascending order)
current holds the combination being built

2. Base Case

When current.length === k, we have selected k numbers
Push a copy of current into result and return

3. Iterate Through Choices

Loop from start to n
For each value i, add it to current and recurse with start = i + 1
This ensures each number is used at most once and combinations are generated in ascending order

4. Backtrack

After recursion, remove the last element with pop()
This restores the state so the next value can be tried at the current position

5. Return the Result

Sort the result lexicographically for consistent output
Return the complete list of combinations

Key Insight

By always picking numbers in ascending order (starting from start), we naturally avoid duplicate combinations without any extra checks
The recursion tree has at most C(n, k) leaves, each producing one valid combination

Time

**O(k * C(n, k))** — there are C(n, k) combinations and each takes O(k) to copy

Space

O(k)recursion depth is at most k

Solution Code

Permutations II

Combination Sum