Problem

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

You may return the answer in any order.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: n = 4, k = 2
Output:

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

Example 2:

1
2

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

Solution

Method 1 – Backtracking (DFS)

Intuition

To generate all combinations of k numbers from 1 to n, we can use backtracking to build each combination step by step, exploring all possible choices at each step.

Approach

  1. Start with an empty combination and a starting number 1.
  2. At each step, add the next number to the current combination and recurse.
  3. If the combination reaches size k, add it to the answer.
  4. Backtrack by removing the last number and trying the next possible number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> cur;
        function<void(int)> dfs = [&](int start) {
            if (cur.size() == k) { ans.push_back(cur); return; }
            for (int i = start; i <= n; ++i) {
                cur.push_back(i);
                dfs(i+1);
                cur.pop_back();
            }
        };
        dfs(1);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func combine(n int, k int) [][]int {
    var ans [][]int
    var cur []int
    var dfs func(int)
    dfs = func(start int) {
        if len(cur) == k {
            tmp := make([]int, k)
            copy(tmp, cur)
            ans = append(ans, tmp)
            return
        }
        for i := start; i <= n; i++ {
            cur = append(cur, i)
            dfs(i+1)
            cur = cur[:len(cur)-1]
        }
    }
    dfs(1)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        dfs(1, n, k, cur, ans);
        return ans;
    }
    private void dfs(int start, int n, int k, List<Integer> cur, List<List<Integer>> ans) {
        if (cur.size() == k) {
            ans.add(new ArrayList<>(cur));
            return;
        }
        for (int i = start; i <= n; i++) {
            cur.add(i);
            dfs(i+1, n, k, cur, ans);
            cur.remove(cur.size()-1);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun combine(n: Int, k: Int): List<List<Int>> {
        val ans = mutableListOf<List<Int>>()
        val cur = mutableListOf<Int>()
        fun dfs(start: Int) {
            if (cur.size == k) {
                ans.add(cur.toList())
                return
            }
            for (i in start..n) {
                cur.add(i)
                dfs(i+1)
                cur.removeAt(cur.size-1)
            }
        }
        dfs(1)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        ans = []
        cur = []
        def dfs(start: int):
            if len(cur) == k:
                ans.append(cur[:])
                return
            for i in range(start, n+1):
                cur.append(i)
                dfs(i+1)
                cur.pop()
        dfs(1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
        fn dfs(n: i32, k: i32, start: i32, cur: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
            if cur.len() == k as usize {
                ans.push(cur.clone());
                return;
            }
            for i in start..=n {
                cur.push(i);
                dfs(n, k, i+1, cur, ans);
                cur.pop();
            }
        }
        let mut ans = vec![];
        let mut cur = vec![];
        dfs(n, k, 1, &mut cur, &mut ans);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    combine(n: number, k: number): number[][] {
        const ans: number[][] = [];
        const cur: number[] = [];
        function dfs(start: number) {
            if (cur.length === k) {
                ans.push([...cur]);
                return;
            }
            for (let i = start; i <= n; i++) {
                cur.push(i);
                dfs(i+1);
                cur.pop();
            }
        }
        dfs(1);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(C(n, k) * k), where C(n, k) is the number of combinations. Each combination takes O(k) to build.
  • 🧺 Space complexity: O(C(n, k) * k), for storing all combinations.