Problem Explanation

You are given two integers n and k. You are asked to find all possible combinations of k numbers out of the sequence from 1 to n.

For instance, let's say n = 4 and k = 2. The possible combinations of 2 numbers out of n = 4 sequence [1, 2, 3, 4] would be:

1
2
3[
4    [1, 2],
5    [1, 3],
6    [1, 4],
7    [2, 3],
8    [2, 4],
9    [3, 4]
10]

Solution Walkthrough

To solve this problem, we can use a recursive depth-first search (DFS) approach, which is a common strategy for searching or exploring through a tree or graph data.

The algorithm works as follows:

1. Create a function called dfs.
2. If the size of the path, our current combination, equals k, we add path to our answer set and return.
3. Otherwise, for each integer from s to n, append the integer to path (path.push_back(i)) and call dfs recursively, considering the next number (i + 1).

We're utilizing the fact that each number can be included once, and the order doesn't matter, hence, we increment i + 1 each recursion so we don't return to previous values.

Solution

Python

1
2python
3class Solution:
4    def combine(self, n: int, k: int) -> List[List[int]]:
5        def dfs(n, k, index, path, res):
6            if len(path) == k:
7                res.append(path)
8                return 
9            for i in range(index, n + 1):
10                dfs(n, k, i + 1, path + [i], res)
11            
12        res = []
13        dfs(n, k, 1, [], res)
14        return res

Java

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

JavaScript

1
2javascript
3var combine = function(n, k) {
4    const result = [];
5    function dfs(n, k, start, path) {
6        if (path.length === k) {
7            result.push([...path]);
8            return;
9        }
10        for (let i = start; i <= n; i++) {
11            path.push(i);
12            dfs(n, k, i + 1, path);
13            path.pop();
14        }
15    }
16    dfs(n, k, 1, []);
17    return result;
18};
19
20## C++
21

c++ class Solution { public: vector<vector> combine(int n, int k) { vector<vector> result; dfs(n, k, 1, {}, result); return result; }

private: void dfs(int n, int k, int start, vector path, vector<vector>& result) { if (path.size() == k) { result.push_back(path); return; } for (int i = start; i <= n; ++i) { path.push_back(i); dfs(n, k, i + 1, path, result); path.pop_back(); } } };

1
2
3
4## C#
5

csharp public class Solution { public IList<IList> Combine(int n, int k) { IList<IList> result = new List<IList>(); DFS(n, k, 1, new List(), result); return result; }

1private void DFS(int n, int k, int index, List<int> path, IList<IList<int>> result) {
2    if (path.Count == k) {
3        result.Add(new List<int>(path));
4        return;
5    }
6    for (int i = index; i <= n; i++) {
7        path.Add(i);
8        DFS(n, k, i + 1, path, result);
9        path.RemoveAt(path.Count - 1);
10    }
11}

}

1
2# Explanation of Code
3
4All the codes in different languages follow the same logic to solve the problem. We start by declaring the main function which initiates the recursive function i.e., dfs. Here are the steps that the function will follow:
5
6- The function `dfs` is passed five parameters - `n`, `k`, the `index` from where we should start, `path` (the current combination), and `res` (the final result list).
7- Within this function, we first check if the size of `path` is equal to `k`. If it is, then we add path to `result` and return to stop further recursion.
8- If the length of `path` is not yet equal to `k`, we use a for loop to iterate from the `index` to `n`. For each `i`, we recursively call `dfs`, passing it `n`, `k`, the incremented index `i + 1`, the updated path, which now includes `i`, and `result`.
9
10The different iterations continue until all possible combinations are explored and added to `result`, which is returned at the end. The languages all required a slightly different syntax but the main function and logic remained the same.
11
12Although the overall complexity of the solution is O(n^k), which could be costly in terms of both time and space if n and k are large, this approach benefits from its simplicity and wide applicability. The strategy used in the solution, DFS, is a powerful tool for navigating through complex structures and can be applied in different scenarios with slight modifications, making it a useful technique to master.