简单的谈谈dfs

简单的说回溯法，递归就是将函数负责几遍。那么回溯法就是将for循环复制几遍。
回溯法框架

public class Solution {
    public static List<List<Integer>> ans=new LinkedList<List<Integer>>();//存储最后的结果集合
    public static boolean[] v=new boolean[100];//用来标记某个元素是否被使用过了
    public static LinkedList<Integer> list=new LinkedList<Integer>();//用来存储每一层递归的结果
    public static void robot(int index,int[] nums){
        if () {//递归出口
            System.out.println(list);
            List<Integer> list2=new LinkedList<Integer>();
            for (Integer i : list) {
                list2.add(i);
            }
            ans.add(list2);//不能存list到最后会被清空
            return;
        }
        for(){
        //一般都有list.add(xxx)
        //一般都有list.pollLast();
        }
    }

}

为什么要把list的最后一层给pop出来呢？因为集合和数组一样都是传的指针，就对下一个函数传指针调用，所以即使被调用的函数消失也会影响集合里面的值。所有当我们回到递归的上一层时，我们是想回到调用函数的那个状态，所有我们需要把影响的值给去掉。

我们现在在看看有返回值的递归：

public int TreeDepth(TreeNode root, int sum) {
        if (root == null) {
            return sum; //这里返回的值的意义要和其他的返回值的意义样
        }
        int left = TreeDepth(root.left, sum + 1);
        int right = TreeDepth(root.right, sum + 1);
        int deepth = Math.max(left, right);
        return deepth; // //这里返回的值的意义要和其他的返回值的意义样

    }

对于有一些题目可以从“要么取，要么不取”只有两种状态的，我们可以参考二叉树的三种遍历来思考。
对对于一些题目是有多种状态可以看出多给个for循环的嵌套。比如：8皇后可以看出是8个for循环的嵌套来解决。对于n皇后则可以看成是n个for循环所以要使用dfs，因为n是一个变量