问题描述
https://leetcode.com/problems/combinations/#/description
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
For example, If n = 4 and k = 2, a solution is:
[
[
2,
4],
[
3,
4],
[
2,
3],
[
1,
2],
[
1,
3],
[
1,
4],
]
算法
类似全排列问题，使用回溯算法即可
代码
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res
= new ArrayList
<List<Integer>>();
fun(res,
new ArrayList
<Integer>(),
0, n, k);
return res;
}
public void fun(
List<List<Integer>> res,
List<Integer> list, int start, int n, int k) {
if(
list.size()
== k) {
res
.add(
new ArrayList
<>(
list));
return;
}
for(int i
=start;i
<n;i
++) {
list.add(i
+1);
fun(res,
list, i
+1, n, k);
list.remove(
list.size()
-1);
}
}
