蒟蒻研究了半天的回溯得出的心得：
回溯这不就是纯纯暴力搜索吗？
题目描述：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
因为如果直接用for循环来嵌套搜索，你不知道需要多少层的循环，从而需要使用递归。
而在递归代码中的for循环就是枚举了第一个元素的可能情况，可以将他看作是最外层的循环，内层的循环交由递归去实现，内层的递归则是逐一枚举了第2、3、4……k个元素的可能情况。
public void f(int n,int k,int i){
if(path.size()==k){
ans.add(new ArrayList<>(path));
return;
}
for(int j=i;j<=n;j++){
path.add(j);
f(n,k,j+1);
path.removeLast();
}
}以n=3,k=2说明，外层循环相当于for(j=1;j<=n;j++)首先选择数字1，加入到路径中，此时便确定了第一个元素之后再确定第二个元素。递归f(n,k,j+1)，不就是枚举第二个元素的可能情况吗？这时候不理解的j+1也一目了然，不就是相当于for(j+1;j<=n;j++),他不就是相当于再进入了一层for循环吗？之后当path.size()==k时，就说明获得了其中一种情况，将其加入到ans中，之后删除路径中的最后一个元素，此为回溯，而这时的回溯不就是倒回到了最后一层for循环吗？接着枚举其余可能的情况（我想我说的挺清楚了），依次类推整个结果就出来
class Solution {
List<List<Integer>> ans=new ArrayList<>();
List<Integer> path=new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
f(n,k,1);
return ans;
}
public void f(int n,int k,int i){
if(path.size()==k){
ans.add(new ArrayList<>(path));
return;
}
for(int j=i;j<=n;j++){ //枚举第一个数字
path.add(j);
f(n,k,j+1); //枚举第二个，第三个……直到第n个
path.removeLast();
}
}
}评论 (0)
