Question

Formatted question description: https://leetcode.ca/all/77.html

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 <= 20
• 1 <= k <= n

Algorithm

DFS

Depth-first search DFS to solve, create a large set res that saves the final result, and define a small set out that saves each combination, and put one count into out each time.

If the number in out reaches k, then Save out to the final result, otherwise continue to call recursion in the next layer.

Iteration

Each time the rightmost number is incremented and stored in the result res. When the right number exceeds n, the left number is increased, and then the current array is assigned to the left number, and then incremented one by one until the leftmost number is also If n is exceeded, the loop is stopped.

For n=4, k=2, the order of traversal is as follows:

0 0 #initialization
1 0
1 1
1 2 #push_back
1 3 #push_back
1 4 #push_back
1 5
2 5
2 2
2 3 #push_back
2 4 #push_back
...
3 4 #push_back
3 5
4 5
4 4
4 5
5 5 #stop


Code

• public class Combinations {

public class Solution_dfs {

List<List<Integer>> result = new ArrayList<>();
List<Integer> tmp = new ArrayList<>();

public List<List<Integer>> combine(int n, int k) {

if (k > n || n <= 0 || k <= 0) {
return result;
}

dfs(n, k, 1);

return result;

}

private void dfs(int n, int k, int start) {

if (k == 0) {
result.add(new ArrayList<>(tmp));
return;
}

for (int i = start; i <= n; i++) {
tmp.add(i);
dfs(n, k - 1, i + 1);
tmp.remove(tmp.size() - 1);
}

}
}

public class Solution_iteration {
public List<List<Integer>> combine(int n, int k) {

List<List<Integer>> res = new ArrayList<>();
int[] out = new int[k];

int i = 0;
while (i >= 0) {
++out[i];
if (out[i] > n) --i;
else if (i == k - 1) res.add(Arrays.stream(out).boxed().collect(Collectors.toList()));
else {
++i;
out[i] = out[i - 1];
}
}

return res;
}
}

}

############

class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
dfs(1, n, k, new ArrayList<>(), res);
return res;
}

private void dfs(int i, int n, int k, List<Integer> t, List<List<Integer>> res) {
if (t.size() == k) {
res.add(new ArrayList<>(t));
return;
}
for (int j = i; j <= n; ++j) {
t.add(j);
dfs(j + 1, n, k, t, res);
t.remove(t.size() - 1);
}
}
}

• // OJ: https://leetcode.com/problems/combinations/
// Time: O(K!)
// Space: O(K)
class Solution {
vector<vector<int>> ans;
void dfs(int n, int k, int start, vector<int> &tmp) {
if (tmp.size() == k) {
ans.push_back(tmp);
return;
}
for (int i = start, end = n - k + tmp.size(); i <= end; ++i) {
tmp.push_back(i + 1);
dfs(n, k, i + 1, tmp);
tmp.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
vector<int> tmp;
dfs(n, k, 0, tmp);
return ans;
}
};

• class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []

def dfs(i, t):
# no need to check len(t)>k, when '==k' returned already
if len(t) == k:
res.append(t.copy())
return
for j in range(i, n + 1):
t.append(j)
dfs(j + 1, t)
t.pop()

dfs(1, [])
return res

class Solution_iteration:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
out = [0] * k
i = 0

while i >= 0:
out[i] += 1
if out[i] > n:
i -= 1
elif i == k - 1:
res.append(list(out))
else:
i += 1
out[i] = out[i - 1]

return res

############

class Solution(object):
def combine(self, n, k):
if k == 1:
return [[i] for i in range(1, n + 1)]
elif k == n:
return [[i for i in range(1, n + 1)]]
else:
rs = []
rs += self.combine(n - 1, k)
part = self.combine(n - 1, k - 1)
for ls in part:
ls.append(n)
rs += part
return rs


• func combine(n int, k int) [][]int {
var res [][]int
var t []int
dfs(1, n, k, t, &res)
return res
}

func dfs(i, n, k int, t []int, res *[][]int) {
if len(t) == k {
cp := make([]int, k)
copy(cp, t)
*res = append(*res, cp)
return
}
for j := i; j <= n; j++ {
t = append(t, j)
dfs(j+1, n, k, t, res)
t = t[:len(t)-1]
}
}

• function combine(n: number, k: number): number[][] {
const res: number[][] = [];
const dfs = (i: number, t: number[]) => {
if (t.length == k) {
res.push(t);
return;
}
// 剪枝
if (t.length + n - i + 1 < k) {
return;
}
for (let j = i; j <= n; j++) {
dfs(j + 1, [...t, j]);
}
};
dfs(1, []);
return res;
}


• impl Solution {
fn dfs(i: i32, n: i32, k: i32, t: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
if k == 0 {
res.push(t.clone());
return;
}
// 剪枝
if n - i + 1 < k {
return;
}
for j in i..=n {
t.push(j);
Self::dfs(j + 1, n, k - 1, t, res);
t.pop();
}
}

pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
let mut res = vec![];
Self::dfs(1, n, k, &mut vec![], &mut res);
res
}
}


• 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);
}
}
}