步骤:
- 画出解空间树型图
- 根据经验写出dfs需要的参数
- 写上结束条件
- 根据树型图写出for循环,并与图中每一层比较是否对应
- 接下来套回溯模版即可
- 若返回值需要存入数据结构且会被回溯清空,需要另外备份一份才能存入
使用案例1:leetcode77 组合
配套使用方法:
- 假设n=4,k=3,则画出树型图如下:
- 思考dfs需要的参数:n,k,当前到第几个数了index,当前的临时tempList
- 结束条件:index到n,说明已经找到一个解了
- for循环:若index=0,则从1开始,否则从上一个存入的数+1开始,一直到k结束
代码答案:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public List<List<Integer>> ans = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
dfs(k,0,new LinkedList<Integer>(),n);
return ans;
}
public void dfs(int numOfList,int curindex,List<Integer> temp,int maxNum){
if(curindex == numOfList){
ans.add(new LinkedList<Integer>(temp));
return;
}
for(int i = (temp.isEmpty() ? 1 :temp.get(curindex-1)+1);i <= maxNum;i++){
temp.add(i);
dfs(numOfList,curindex+1,temp,maxNum);
temp.remove(curindex);
}
}