Generate All k-Number Combinations from 1 to n (LeetCode 77)

Problem Description

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. The order of the combinations in the output does not matter.

Examples

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

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

Constraints

1 ≤ n ≤ 20

1 ≤ k ≤ n

Problem Analysis

The task is to generate combinations, which are unordered selections of k distinct numbers. A natural way to solve this is with backtracking: build a tree where each level adds a new number, always choosing numbers larger than the previously selected one to avoid duplicate permutations such as [1,2] and [2,1]. When the current path reaches length k, add a copy to the result list.

Java Solution

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(ans, new ArrayList<>(), 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++ Solution

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 Solution

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

Illustrative Diagram