回溯法(+DFS):注意理解回溯的地方是重点(LC77)
回溯法的核心是回溯。在搜索到某一节点的时候,如果我们发现目前的节点(及其子节点)并不是需求目标时,我们回退到原来的节点继续搜索,并且把在目前节点修改的状态还原。这样的好处是我们可以始终只对图的总状态进行修改,而非每次遍历时新建一个图来储存状态。
在具体的写法上,它与普通的深度优先搜索一样,都有 [修改当前节点状态]→[递归子节
点] 的步骤,只是多了回溯的步骤,变成了 [修改当前节点状态]→[递归子节点]→[回改当前节点
状态]。
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res=new ArrayList<>();
if(k<=0||n<k){
return res;
}
//从1开始是题目的设定
//叶子结点的信息体现在从根结点到叶子结点的路径上,因此需要一个表示路径的变量 path
//它是一个列表,特别地,path 是一个栈;
Deque<Integer> path=new ArrayDeque<>();
dfs(n,k,1,path,res);
return res;
}
private void dfs(int n,int k,int begin,Deque<Integer> path, List<List<Integer>>res){
//递归结束条件:path的长度=k
if(path.size()==k){
res.add(new ArrayList<>(path));
return;
}
//遍历可能的搜索起点
for(int i=begin;i<=n;i++){
//想路径添加一个数
path.addLast(i);
//下一轮搜索,设置起点+1,因为组合数里不允许出现重复的元素
dfs(n,k,i+1,path,res);
// 重点理解这里:深度优先遍历有回头的过程,因此递归之前做了什么,递归之后需要做相同操作的逆向操作
path.removeLast();
}
}
}