Leetcode 77. Combinations
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:
- Create a function called
dfs
. - If the size of the
path
, our current combination, equalsk
, we addpath
to our answer set and return. - Otherwise, for each integer from
s
ton
, append the integer topath
(path.push_back(i)
) and calldfs
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
private:
void dfs(int n, int k, int start, vector
1 2 3 4## C# 5
csharp
public class Solution {
public IList<IList
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.