Master LeetCode 77: Generate All Combinations with Java, C++, and Python

Problem Description

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. The order of numbers inside each combination does not matter, and the overall order of the returned combinations is irrelevant.

Examples

Example 1 : Input

n = 4, k = 2

[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

Example 2 : Input

n = 1, k = 1

[[1]]

Constraints

1 ≤ n ≤ 20

1 ≤ k ≤ n

Algorithm Overview

The task is a classic backtracking problem. We build combinations by exploring a depth‑first search tree where each level adds one new number to the current partial combination ( path). To avoid duplicate combinations we always choose the next number from the remaining larger numbers (i.e., the next recursive call starts at start = previous + 1). When the length of path reaches k, we have a complete combination and add a copy of path to the result list.

Reference Implementations

Java

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(ans, new ArrayList<>(k), n, k, 1);
    return ans;
}

private void dfs(List<List<Integer>> ans, List<Integer> path, int n, int k, int start) {
    if (path.size() == k) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i <= n; i++) {
        path.add(i);               // choose
        dfs(ans, path, n, k, i + 1); // recurse
        path.remove(path.size() - 1); // backtrack
    }
}

C++

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> ans;
    vector<int> path;
    dfs(ans, path, n, k, 1);
    return ans;
}

void dfs(vector<vector<int>>& ans, vector<int>& path, int n, int k, int start) {
    if (path.size() == k) {
        ans.emplace_back(path);
        return;
    }
    for (int i = start; i <= n; ++i) {
        path.emplace_back(i);          // choose
        dfs(ans, path, n, k, i + 1);   // recurse
        path.pop_back();               // backtrack
    }
}

Python

def combine(self, n: int, k: int) -> List[List[int]]:
    ans = []
    path = []
    def dfs(start: int):
        if len(path) == k:
            ans.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)          # choose
            dfs(i + 1)              # recurse
            path.pop()               # backtrack
    dfs(1)
    return ans

Complexity Analysis

The algorithm generates C(n, k) combinations, each of length k. The time complexity is O(k · C(n, k)) because each combination requires k operations to copy. The auxiliary space used by the recursion stack is O(k), not counting the output list.