77. Combinations
Description
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2 Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Explanation: There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1 Output: [[1]] Explanation: There is 1 choose 1 = 1 total combination.
Constraints:
1 <= n <= 201 <= k <= n
Solutions
Solution 1: Backtracking (Two Ways)
We design a function $dfs(i)$, which represents starting the search from number $i$, with the current search path as $t$, and the answer as $ans$.
The execution logic of the function $dfs(i)$ is as follows:
If the length of the current search path $t$ equals $k$, then add the current search path to the answer and return.
If $i \gt n$, it means the search has ended, return.
Otherwise, we can choose to add the number $i$ to the search path $t$, and then continue the search, i.e., execute $dfs(i + 1)$, and then remove the number $i$ from the search path $t$; or we do not add the number $i$ to the search path $t$, and directly execute $dfs(i + 1)$.
The above method is actually enumerating whether to select the current number or not, and then recursively searching the next number. We can also enumerate the next number $j$ to be selected, where $i \leq j \leq n$. If the next number to be selected is $j$, then we add the number $j$ to the search path $t$, and then continue the search, i.e., execute $dfs(j + 1)$, and then remove the number $j$ from the search path $t$.
In the main function, we start the search from number $1$, i.e., execute $dfs(1)$.
The time complexity is $(C_n^k \times k)$, and the space complexity is $O(k)$. Here, $C_n^k$ represents the combination number.
Similar problems:
Python3
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def dfs(i: int):
if len(t) == k:
ans.append(t[:])
return
if i > n:
return
t.append(i)
dfs(i + 1)
t.pop()
dfs(i + 1)
ans = []
t = []
dfs(1)
return ans
Java
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int n;
private int k;
public List<List<Integer>> combine(int n, int k) {
this.n = n;
this.k = k;
dfs(1);
return ans;
}
private void dfs(int i) {
if (t.size() == k) {
ans.add(new ArrayList<>(t));
return;
}
if (i > n) {
return;
}
t.add(i);
dfs(i + 1);
t.remove(t.size() - 1);
dfs(i + 1);
}
}
C++
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> ans;
vector<int> t;
function<void(int)> dfs = [&](int i) {
if (t.size() == k) {
ans.emplace_back(t);
return;
}
if (i > n) {
return;
}
t.emplace_back(i);
dfs(i + 1);
t.pop_back();
dfs(i + 1);
};
dfs(1);
return ans;
}
};
Go
func combine(n int, k int) (ans [][]int) {
t := []int{}
var dfs func(int)
dfs = func(i int) {
if len(t) == k {
ans = append(ans, slices.Clone(t))
return
}
if i > n {
return
}
t = append(t, i)
dfs(i + 1)
t = t[:len(t)-1]
dfs(i + 1)
}
dfs(1)
return
}
TypeScript
function combine(n: number, k: number): number[][] {
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number) => {
if (t.length === k) {
ans.push(t.slice());
return;
}
if (i > n) {
return;
}
t.push(i);
dfs(i + 1);
t.pop();
dfs(i + 1);
};
dfs(1);
return ans;
}
Rust
impl Solution {
fn dfs(i: i32, n: i32, k: i32, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if t.len() == (k as usize) {
ans.push(t.clone());
return;
}
if i > n {
return;
}
t.push(i);
Self::dfs(i + 1, n, k, t, ans);
t.pop();
Self::dfs(i + 1, n, k, t, ans);
}
pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
let mut ans = vec![];
Self::dfs(1, n, k, &mut vec![], &mut ans);
ans
}
}
C#
public class Solution {
private List<IList<int>> ans = new List<IList<int>>();
private List<int> t = new List<int>();
private int n;
private int k;
public IList<IList<int>> Combine(int n, int k) {
this.n = n;
this.k = k;
dfs(1);
return ans;
}
private void dfs(int i) {
if (t.Count == k) {
ans.Add(new List<int>(t));
return;
}
if (i > n) {
return;
}
t.Add(i);
dfs(i + 1);
t.RemoveAt(t.Count - 1);
dfs(i + 1);
}
}
Solution 2
Python3
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def dfs(i: int):
if len(t) == k:
ans.append(t[:])
return
if i > n:
return
for j in range(i, n + 1):
t.append(j)
dfs(j + 1)
t.pop()
ans = []
t = []
dfs(1)
return ans
Java
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int n;
private int k;
public List<List<Integer>> combine(int n, int k) {
this.n = n;
this.k = k;
dfs(1);
return ans;
}
private void dfs(int i) {
if (t.size() == k) {
ans.add(new ArrayList<>(t));
return;
}
if (i > n) {
return;
}
for (int j = i; j <= n; ++j) {
t.add(j);
dfs(j + 1);
t.remove(t.size() - 1);
}
}
}
C++
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> ans;
vector<int> t;
function<void(int)> dfs = [&](int i) {
if (t.size() == k) {
ans.emplace_back(t);
return;
}
if (i > n) {
return;
}
for (int j = i; j <= n; ++j) {
t.emplace_back(j);
dfs(j + 1);
t.pop_back();
}
};
dfs(1);
return ans;
}
};
Go
func combine(n int, k int) (ans [][]int) {
t := []int{}
var dfs func(int)
dfs = func(i int) {
if len(t) == k {
ans = append(ans, slices.Clone(t))
return
}
if i > n {
return
}
for j := i; j <= n; j++ {
t = append(t, j)
dfs(j + 1)
t = t[:len(t)-1]
}
}
dfs(1)
return
}
TypeScript
function combine(n: number, k: number): number[][] {
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number) => {
if (t.length === k) {
ans.push(t.slice());
return;
}
if (i > n) {
return;
}
for (let j = i; j <= n; ++j) {
t.push(j);
dfs(j + 1);
t.pop();
}
};
dfs(1);
return ans;
}
Rust
impl Solution {
fn dfs(i: i32, n: i32, k: i32, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if t.len() == (k as usize) {
ans.push(t.clone());
return;
}
if i > n {
return;
}
for j in i..=n {
t.push(j);
Self::dfs(j + 1, n, k, t, ans);
t.pop();
}
}
pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
let mut ans = vec![];
Self::dfs(1, n, k, &mut vec![], &mut ans);
ans
}
}
C#
public class Solution {
private List<IList<int>> ans = new List<IList<int>>();
private List<int> t = new List<int>();
private int n;
private int k;
public IList<IList<int>> Combine(int n, int k) {
this.n = n;
this.k = k;
dfs(1);
return ans;
}
private void dfs(int i) {
if (t.Count == k) {
ans.Add(new List<int>(t));
return;
}
if (i > n) {
return;
}
for (int j = i; j <= n; ++j) {
t.Add(j);
dfs(j + 1);
t.RemoveAt(t.Count - 1);
}
}
}