https://leetcode-cn.com/problems/combinations/
给定两个整数 n
和 k
,返回 1 ... n
中所有可能的 k
个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
n=4,k=3
时,如果列表从start=3
也就是[3]
开始,那么该组合一定不存在,因为至少要k=3
个数据,所以剪枝临界点为n-balance+1
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
getCombine(n, k, 1, new ArrayList<>());
return ans;
}
public void getCombine(int n, int k, int start, List<Integer> list) {
if(k == 0) {
ans.add(new ArrayList<>(list));
return;
}
for(int i = start;i <= n - k + 1;i++) {
list.add(i);
getCombine(n, k - 1, i+1, list);
list.remove(list.size() - 1);
}
}
}