回溯法代码模板

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;  不需要

        }

    }

解释如下:

回溯法代码模板

 

上一篇:stat /bin/bash: no such file or directory“: unknown.


下一篇:qemu之linux-user备忘