给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
分析:回溯算法的入门题,回溯算法是暴力解法的优化版,是到了不用暴力解法做不出来的题目,需要列举所有可能的情况的题目时,所用的算法,主要是通过递归中保存原有相同的状态来减少计算
分为三个点:函数参数,终止条件,循环过程
函数参数是指递归函数要传的参数,而返回值一般是void,
终止条件即什么时候路径中的值可以传入结果了,就不用继续递归了,而是返回
循环过程即单层循环的逻辑
参考代码:
public List> combine(int n, int k) {
sup(n,1,k);
return ret;
}
//公共变量,方便使用
List> ret = new ArrayList<>();
LinkedList
//递归函数,返回值为void,需要三个参数,最大递归n,当前递归index以及终止变量k
private void sup(int n,int index,int k){
//终止条件:当路径中的值的数量=k时,就表示可以返回了
if(path.size()==k){
ret.add(new ArrayList<>(path));
return;
}
//单层 递归,组合问题从index开始循环,到最大递归n结束
for(int i=index;i<=n;i++){
//加入新的值
path.add(i);
//递归!
sup(n,i+1,k);
//回溯!
path.removeLast();
}
}
