void dfs(参数) {
if (终止条件) {
创建工作数组的副本;
(有时候需要:对副本进行操作(例如排序);)
存放操作后的副本;
return; //必不可少
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
if(判断是否符合递归下去的条件){
路径中加入当前结点;
dfs(参数); // 递归
回溯,撤销影响
}
}
// 不需要return
} //end dfs()
举例如下:
public void dfs(int[] candidates, int target, LinkedList<Integer> tem) {
if (target == 0) {
ArrayList<Integer> tt = new ArrayList<>(tem);
Collections.sort(tt);
res.add(tt);
return;
}
if (target < 0) {
return;
}
for (int i = 0; i < candidates.length; i++) {
if (target >= 0) {
tem.add(candidates[i]);
dfs(candidates, target - candidates[i], tem);
tem.removeLast();
}
}
// return; 不需要
}
}
解释如下: