Difficulty: MediumBacktracking

Combinations

Problem in Plain English

Given n and k, return every unique group of k distinct numbers drawn from 1 through n. Each group is listed once and the answer order does not matter.

Problem Statement

Given two integers n and k, return every possible combination of k distinct numbers chosen from 1 to n.

List each combination in increasing order, since rearrangements of the same numbers count as one combination.

The full answer may come back in any order.

Constraints

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

Examples

Example 1

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

Choosing 1 produces [1, 2], [1, 3] and [1, 4]; choosing 2 next produces [2, 3] and [2, 4]; choosing 3 produces [3, 4]. These are the six different pairs. Reversing a pair does not create a new group.

Example 2

Input: n = 1, k = 1
Output: [[1]]

The range holds a single number, so the only combination is [1].

Example 3

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

All four numbers are required, so skipping even one makes completion impossible. There is exactly one group, although its elements could be rearranged in many ways; rearrangements are not new combinations.

Example 4

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

Only one slot needs filling, so every number individually completes a group. No pair belongs in this output.

Intuition

A combination is a group, so [1, 2] and [2, 1] must not become separate answers. Represent each group by its increasing sequence. In Example 1, choosing 1 leaves only 2, 3 and 4 for the second position; after those pairs, starting with 2 leaves only 3 and 4. A start index enforces this order, and the number of empty slots tells us when too few larger numbers remain.

Approaches

Bitmask Filter

Solution Details

Reveal Bitmask Filter: intuition, complexity, and code

Intuition

Encode a subset with one bit for each number, then scan every mask and retain only subsets of size k. Bit i corresponds to number i + 1. This gives an exhaustive baseline, but most of its work constructs subsets of the wrong size; Example 1 accepts only six of its sixteen masks.

Step-by-Step Logic

Enumerate masks from zero through one less than $2^n$ . For Example 1 this visits all sixteen masks from 0 through 15.
For each mask create a fresh list, then examine each bit index i from 0 through n - 1. A set bit adds i + 1, so mask 3 (0011) builds [1, 2].
After inspecting every bit, retain the list only if its length equals k. Example 1 accepts masks 3, 5, 6, 9, 10 and 12; mask 7 is rejected because it selects three numbers.
Return the retained lists. Their traversal order is [[1,2],[1,3],[2,3],[1,4],[2,4],[3,4]], which represents exactly the same six groups as Example 1; answer order is unrestricted.

Why It Works

Each subset corresponds to exactly one mask: bit i is set precisely when number i + 1 belongs to it. Enumerating all masks therefore covers every subset without duplicates. Reading bits from smallest to largest index builds an increasing list of distinct values. Retaining exactly the lists of length k excludes every invalid size and includes every required combination.

Dry Run

Bitmask Filter: variable states at each step
mask	bits (4 to 1)	list after scanning bits 0 to 3	size / action	retained count
0	0000	[]	0 / discard	0
1	0001	[1]	1 / discard	0
2	0010	[2]	1 / discard	0
3	0011	[1,2]	2 / keep	1
4	0100	[3]	1 / discard	1
5	0101	[1,3]	2 / keep	2
6	0110	[2,3]	2 / keep	3
7	0111	[1,2,3]	3 / discard	3
8	1000	[4]	1 / discard	3
9	1001	[1,4]	2 / keep	4
10	1010	[2,4]	2 / keep	5
11	1011	[1,2,4]	3 / discard	5
12	1100	[3,4]	2 / keep	6
13	1101	[1,3,4]	3 / discard	6
14	1110	[2,3,4]	3 / discard	6
15	1111	[1,2,3,4]	4 / discard	6
return	all masks exhausted	[[1,2],[1,3],[2,3],[1,4],[2,4],[3,4]]	same six groups as Example 1	6

Complexity Analysis

Time Complexity

O(n \cdot 2^n)

Space Complexity

O(n)

Every one of the 2^n masks scans n bits, so time is O(n * 2^n), including building temporary lists and retained output. At most O(n) temporary list storage is live beyond the answer, although O(n * 2^n) entries are allocated across all masks. Let B = C(n, k), the number of combinations: returned lists use O(k * B) space, making total live space O(n + k * B). The space bound shown excludes output. Since n <= 20, Java and JavaScript shifts stay within their safe signed 32-bit range.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3
4class Solution {5    public List<List<Integer>> combine(int n, int k) {6        List<List<Integer>> res = new ArrayList<>();7        for (int mask = 0; mask < (1 << n); mask++) {8            List<Integer> cur = new ArrayList<>();9            for (int i = 0; i < n; i++) {10                // Bit i selects number i + 1; increasing i gives canonical order.11                if ((mask & (1 << i)) != 0) cur.add(i + 1);12            }13            if (cur.size() == k) res.add(cur);14        }15        return res;16    }17}

Hints

Hint 1

A subset is determined by whether each number is present. How could you represent those choices with bits and retain only size-k subsets?

Hint 2

Increasing choices give each group one representation. After choosing i, what should the next start index be?

Hint 3

If r slots remain, choosing i needs r - 1 larger numbers afterward. Solve that condition for the last allowed i, then copy completed paths before undoing choices.

Edge Cases

n = 1, k = 1 returns [[1]]; the builder reaches its base case after one selection.
k = 1 returns each number alone: n = 4 gives [[1],[2],[3],[4]].
k = n returns only the whole range. The builder loop has one feasible choice at every depth.
n = 20, k = 10 returns 184756 lists holding 1847560 numbers; output storage dominates auxiliary recursion space.

Common Mistakes and Interview Tips

Looping every slot from 1 instead of from the next free number, which builds permutations like [2, 1] alongside [1, 2].
Forgetting to undo the last pick after recursing, so later branches inherit numbers they never chose.
Copying the live path reference into the answer instead of a snapshot, leaving every entry mirroring the final empty path.
Using n - remaining instead of n - remaining + 1 as the inclusive upper bound drops valid boundary choices such as first choice 3 in Example 1.
Treating the two answer orders as different results: the bitmask approach emits [2,3] before [1,4], which is permitted.
Interview tip: separate O(k) auxiliary space from O(k * C(n, k)) returned storage, and explain why shortfall pruning still includes every valid sequence.

Key Takeaway

For fixed-size subsets, keep choices in increasing order to avoid duplicate permutations, then use the number of unfilled slots to exclude prefixes that cannot reach an answer. Copy only complete paths and undo each choice before visiting siblings.