Problem statement

Given integers n and k, return all combinations of k numbers chosen from [1, n], each combination in ascending order, and the list in lexicographic order.

Example 1

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

Example 2

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

Constraints

• 1 <= n <= 7
• 1 <= k <= n

Hints for Combinations

1. Hint 1

   Backtracking: each level picks a number strictly larger than the previous.

2. Hint 2

   Stop the loop early when not enough numbers remain to complete the combination.

How to solve Combinations

A combination is an increasing sequence of k numbers drawn from 1..n. Enforce "increasing" structurally: each recursion level picks a number strictly larger than the previous one by passing i + 1 as the next starting point. That makes every combination reachable by exactly one path, so no duplicates and no need to sort or de-duplicate.

Approach

1. Recurse with a start value and the combination built so far.
2. When the combination holds k numbers, record a copy and stop.
3. Otherwise loop i from start up to n.
4. Append i, recurse with start = i + 1, then remove it.
5. Because each level scans ascending and always moves right, the output is lexicographic.

Why it works

Every k-element subset of 1..n has exactly one increasing arrangement, and the start index forces the search to build precisely that arrangement — so the search visits each combination once and only once. Advancing to i + 1 rather than i is what forbids reusing a number.

Complexity

• Time — O(C(n,k) · k)
• Space — O(C(n,k) · k)

Pitfalls

• The loop bound is inclusive (i <= n) because the numbers are 1..n, not 0..n-1.
• Recursing with i instead of i + 1 allows repeats and turns this into a different problem.
• You can prune hard by stopping once too few numbers remain to reach length k; without it the search still works but explores dead branches.

Reference solution

Python

from typing import List

def combine(n: int, k: int) -> List[List[int]]:
    out = []

    def go(start, cur):
        if len(cur) == k:
            out.append(cur[:])
            return
        for i in range(start, n + 1):
            cur.append(i)
            go(i + 1, cur)
            cur.pop()

    go(1, [])
    return out

Java

public static int[][] combine(int n, int k) {
    List<int[]> out = new ArrayList<>();
    int[] cur = new int[k];
    goCombine(out, n, k, 1, cur, 0);
    return out.toArray(new int[0][]);
}

private static void goCombine(List<int[]> out, int n, int k, int start, int[] cur, int depth) {
    if (depth == k) {
        out.add(cur.clone());
        return;
    }
    for (int i = start; i <= n; i++) {
        cur[depth] = i;
        goCombine(out, n, k, i + 1, cur, depth + 1);
    }
}

C++

void goCombine(vector<vector<int>>& out, int n, int k, int start, vector<int>& cur) {
    if ((int) cur.size() == k) {
        out.push_back(cur);
        return;
    }
    for (int i = start; i <= n; i++) {
        cur.push_back(i);
        goCombine(out, n, k, i + 1, cur);
        cur.pop_back();
    }
}

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> out;
    vector<int> cur;
    goCombine(out, n, k, 1, cur);
    return out;
}

JavaScript

var combine = function(n, k) {
    const out = [];
    function go(start, cur) {
        if (cur.length === k) {
            out.push(cur.slice());
            return;
        }
        for (let i = start; i <= n; i++) {
            cur.push(i);
            go(i + 1, cur);
            cur.pop();
        }
    }
    go(1, []);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More backtracking problems

• Iterator for Combination Medium
• Smallest String Starting From Leaf Medium
• Path Sum II Medium
• Partition String Into Minimum Beautiful Substrings Medium
• Ambiguous Coordinates Medium
• Non-decreasing Subsequences Medium