写一个递归与回溯算法

写一个递归与回溯算法

在我们生活中的树就是一种递归的结构，或者说只要形成了树结构的都可以用递归的方式来处理遍历。主枝干会有很多的分支，每一个分支和主干一样也同样会有其他更多的子分支，每一个更小的分支还会有更多的子分支...

递归本质就是遍历整颗树的一种方式(一个不差的扫描树的每一个叶子获取所有的可能性都这也是递归存在的意义)，从主干开始遍历整颗树和从某一个分支遍历所在的子树本质是一样的，不过是一个更小的问题罢了。当更小的问题解决之后，会自动回到子问题开始的位置，当所有子分支都被解决之后，会回到主枝干一开始解决问题的起始地方，这时候整个问题都被解决了。

递归是由递归的终止条件与更小的子递归问题共同构成了原问题，是一种自顶向下解决问题的算法思维。

斐波那契数列

0 1 1  2 3 5 7 12 ...

如何写一个递归算法

写递归算法的时候，不用考虑调用子递归函数内部具体逻辑是怎么样实现的，想象自然界中的树结构，每一个子分支也是一颗树。调用递归函数会得到更小范围的答案，因为原问题和子问题有着相同的逻辑，所以整个问题都解决了。

比如上面的斐波那契数列，首先要找到规律(是否形成类似于树的递归结构逻辑)，不用想 fib(n-1)+fib(n-2)是怎么执行和计算的。调用 fib(n-1)+fib(n-2)会得到每一个子过程的答案，因为整个逻辑是一样的所以这也一定是最终的答案，所以不用想太多内部的参数与执行的过程，因为逻辑是一样一定会的得到逻辑想要的答案。而调用递归逻辑的时候只用考虑一个问题就是递归的终止条件，n-1与n-2不能一直的执行下去，所以总会有递归的终止条件，根据递归结构来写...

二叉树的前中后序遍历

带入根节点，如果节点不为空的话，前序遍历左孩子之后前序遍历右孩子，因为左孩子与右孩子同样是一颗二叉树

跳出代码是怎么样运行的，具体的语义很清楚就是做一件事情

写递归函数的时候，特别要求空也是一个特殊的二叉树

递归与栈的紧密关系

前序遍历新执行的preorder与原来的preorder没有任何的关系因为传入的参数完全不同，在子函数执行完毕之前原函数都是暂停，执行完毕后会自动退回到上一次暂停的位置继续执行直到整个函数执行完递归结束。

系统栈具体在递归的哪里起作用?

暂停去执行另外的函数这个过程就需要使用栈这种数据结构，往栈中推入的内容就是上一层具体执行到哪里的信息。递归会自动返回到上一层暂停的位置，就是取出栈顶的元素判断该执行哪一步。

遍历右孩子返回的时候，获取栈顶元素信息已经做完了函数里面的所有三件事情，整个子函数结束还要返回上一层还是取出栈顶的元素。

运用栈模拟递归

因为栈的先入后出递归的过程先推入右孩子然后推入左孩子，最后输出。

public List<Integer> inorderTraversal(TreeNode root) {

        ArrayList<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;

        Stack<Command> stack = new Stack<Command>();
        stack.push(new Command("go", root));
        while(!stack.empty()){
            Command command = stack.pop();

            if(command.s.equals("print"))
                res.add(command.node.val);
            else{
                assert command.s.equals("go");
                if(command.node.right != null)
                    stack.push(new Command("go",command.node.right));
                if(command.node.left != null)
                    stack.push(new Command("go",command.node.left));
                stack.push(new Command("print", command.node));
            }
        }
        return res;
    }

栈的其他应用

给定一个字符串看括号是否匹配()[]{} 都是匹配的

如果是左括号的话放入栈中，如果是右括号的话取出栈中的元素判断是否匹配括号。

如果是右括号的话，如果此时栈中没有元素也是没有办法进行匹配，最后判断栈中所有的元素是否都已经匹配过。

public boolean isValid(String s) {
        //Deque<Integer> deque = new LinkedList<>(); //模拟栈
        Stack<Character> stack = new Stack<Character>();
        for( int i = 0 ; i < s.length() ; i ++ )
            if( s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[')
                stack.push(s.charAt(i));
            else{

                if( stack.size() == 0 )
                    return false;

                Character c = stack.pop();

                Character match;
                if( s.charAt(i) == ')' )
                    match = '(';
                else if( s.charAt(i) == ']' )
                    match = '[';
                else{
                    assert s.charAt(i) == '}';
                    match = '{';
                }

                if(c != match)
                    return false;
            }

        if( stack.size() != 0 )
            return false;

        return true;
    }

底层源码集合中寻找某个值

递归实现二叉树的最高深度

首先考虑到的是计算深度到叶子节点就要结束递归并进行统计了，二叉树左右孩子都是同样的遍历逻辑，每次进行递归下一层的时候都会进行+1操作。

如何反转一颗二叉树

首先反转做子树，再反转右子树，然后对整棵树进行反转(左右子树交换位置)

如果传入的时候null，不能反转要进行非空判断

public TreeNode invertTree(TreeNode root) {

        if(root == null)
            return null;

        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        root.left = right;
        root.right = left;

        return root;
    }

判断是否存在从根到叶子节点和为sum的路径

注意递归的终止条件，不能直接判断最后传入的root是否为0，求sum=5时候，因为5不是叶子节点。

node为空判断忽视了父节点是否为叶子节点，如果root为空的话直接访问做子树和右子树会报空指针错误，所以最开始要判空

public boolean hasPathSum(TreeNode root, int sum) {

        if(root == null)
            return false;

        if(root.left == null && root.right == null)
            return sum == root.val;

        return hasPathSum(root.left, sum - root.val)
                || hasPathSum(root.right, sum - root.val);
    }

返回二叉树从根节点到叶子节点的字符串

和现实中的树结构是一样的，整个过程是都是先进入一个枝杈，遍历完了之后回到一开始进入这个枝杈的地方继续遍历别的枝杈，二叉树遍历左子树以及遍历右子树，最后合并在一起。

和指针相关的问题一定要考虑空指针，最后左子树和右子树遍历的结果都会存到res中，返回即可。

public List<String> binaryTreePaths(TreeNode root) {

        ArrayList<String> res = new ArrayList<String>();

        if(root == null)
            return res;

        if(root.left == null && root.right == null){
            res.add(Integer.toString(root.val));
            return res;
        }

        List<String> leftPaths = binaryTreePaths(root.left);
        for(String s: leftPaths){
            StringBuilder sb = new StringBuilder(Integer.toString(root.val));
            sb.append("->");
            sb.append(s);
            res.add(sb.toString());
        }

        List<String> rightPaths = binaryTreePaths(root.right);
        for(String s: rightPaths) {
            StringBuilder sb = new StringBuilder(Integer.toString(root.val));
            sb.append("->");
            sb.append(s);
            res.add(sb.toString());
        }

        return res;
    }

判断路径上有多少条路径，路径上所有节点的和为sum

思维一定要清晰，先考虑与原先的问题有什么不同的地方，往往更加复杂的问题都是由简单基础的问题增加了一定的条件。这个问题也包含了上面从根节点到叶子节点的情况，也包括了不包括根节点到叶子节点的情况，一共这两种情况。

从根节点到叶子节点一样的逻辑，获取左右子树一共有多少个满足条件的记录，然后保存在一开始定义的变量中。如果不包括根节点那么直接从左子树和右子树开始走相同的逻辑。

// 在以root为根节点的二叉树中,寻找和为sum的路径,返回这样的路径个数
    public int pathSum(TreeNode root, int sum) {

        if(root == null)
            return 0;

        return findPath(root, sum)
                + pathSum(root.left , sum)
                + pathSum(root.right , sum);
    }

    // 在以node为根节点的二叉树中,寻找包含node的路径,和为sum
    // 返回这样的路径个数
    private int findPath(TreeNode node, int num){

        if(node == null)
            return 0;

        int res = 0;
        if(node.val == num)
            res += 1;

        res += findPath(node.left , num - node.val);
        res += findPath(node.right , num - node.val);

        return res;
    }

寻找两个节点的二分搜索树的公共祖先

首先要考虑蕴含的递归逻辑，如果p和q都小于node的话，那么最近公共祖先一定不是node，公共祖先在左子树中，同理都大于node在右子树中，如果一个小于node一个大于node那么公共祖先一定是node本身了。

往往会漏掉一种情况，如果p是node本身的话，那么p就是q的公共节点，所以写递归的算法的一开始的时候一定要考虑到所有的递归逻辑情况再去写，一般特殊的情况容易遗漏。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(p == null || q == null)
            throw new IllegalArgumentException("p or q can not be null.");

        if(root == null)
            return null;

        if(p.val < root.val && q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);
        if(p.val > root.val && q.val > root.val)
            return lowestCommonAncestor(root.right, p, q);

        assert p.val == root.val || q.val == root.val
                || (root.val - p.val) * (root.val - q.val) < 0;

        return root;
    }

给定电话按键如23，求所有按键对应的字母和 ，每一个数字对应多个字母如2对应abc、3对应def字符。

仔细发现这个问题也形成了递归树的结构，递归下去的条件是index+1，选a的话会有def三种情况对应，选b也会有三种情况对应，递归的边界就是到达了给定数字组合的长度递归结束。

private String letterMap[] = {
                " ",    //0
                "",     //1
                "abc",  //2
                "def",  //3
                "ghi",  //4
                "jkl",  //5
                "mno",  //6
                "pqrs", //7
                "tuv",  //8
                "wxyz"  //9
    };

    private ArrayList<String> res;

    public List<String> letterCombinations(String digits) {

        res = new ArrayList<String>();
        if(digits.equals(""))
            return res;

        findCombination(digits, 0, "");
        return res;
    }

    // s中保存了此时从digits[0...index-1]翻译得到的一个字母字符串
    // 寻找和digits[index]匹配的字母, 获得digits[0...index]翻译得到的解
    private void findCombination(String digits, int index, String s){

        System.out.println(index + " : " + s);
        if(index == digits.length()){
            res.add(s);
            System.out.println("get " + s + " , return");
            return;
        }

        Character c = digits.charAt(index);
        assert  c.compareTo('0') >= 0 &&
                c.compareTo('9') <= 0 &&
                c.compareTo('1') != 0;
        String letters = letterMap[c - '0'];
        for(int i = 0 ; i < letters.length() ; i ++){
            System.out.println("digits[" + index + "] = " + c +
                    " , use " + letters.charAt(i));
            findCombination(digits, index+1, s + letters.charAt(i));
        }

        System.out.println("digits[" + index + "] = " + c + " complete, return");

        return;
    }

给一个整形数组，每一个元素都不相同求所有的排列结果

发现递归树结构，选一个数组中的一个数字的时候，剩下数字按照同样的逻辑选择一个，直到最后数组中没有元素可以选择自动回溯到最开始的位置，依次选择其他的元素。

递归可以用标识符字段来判断哪个数字已经访问过了，剩余的循环中被标识过的数字不再继续访问，因为递归函数结束之后会自动回溯到开始的地方，但是标识符不能回溯需要手动进行重置操作。

private ArrayList<List<Integer>> res;
    private boolean[] used;

    public List<List<Integer>> permute(int[] nums) {

        res = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0)
            return res;

        used = new boolean[nums.length];
        LinkedList<Integer> p = new LinkedList<Integer>();
        generatePermutation(nums, 0, p);

        return res;
    }

    // p中保存了一个有index-1个元素的排列。
    // 向这个排列的末尾添加第index个元素, 获得一个有index个元素的排列
    private void generatePermutation(int[] nums, int index, LinkedList<Integer> p){

        if(index == nums.length){
            res.add((LinkedList<Integer>)p.clone());
            return;
        }

        for(int i = 0 ; i < nums.length ; i ++)
            if(!used[i]){
                used[i] = true;
                p.addLast(nums[i]);
                generatePermutation(nums, index + 1, p );
                p.removeLast();
                used[i] = false;
            }

        return;
    }

n个数字中选择k个组合的结果(组合结果不能重复，如[1，2]和[2，1]是一样的不能有这种结果)

选择一个数字的时候，每次都从剩余的数组中看还剩几个数然后继续递归的执行，不能有上一次重复的元素。

递归调用结束回来的时候，for循环要尝试其他的元素，这时候回溯要把放入的元素拿出来，for循环中再尝试下一个元素。

递归的剪枝操作，因为要找k个元素在c中已经有了一定的元素，i最多为n-(k-c.size())否则后面c中存放k个元素没有足够的位置。

private ArrayList<List<Integer>> res;

    public List<List<Integer>> combine(int n, int k) {

        res = new ArrayList<List<Integer>>();
        if(n <= 0 || k <= 0 || k > n)
            return res;

        LinkedList<Integer> c = new LinkedList<Integer>();
        generateCombinations(n, k, 1, c);

        return res;
    }

    // 求解C(n,k), 当前已经找到的组合存储在c中, 需要从start开始搜索新的元素
    private void generateCombinations(int n, int k, int start, LinkedList<Integer> c){

        if(c.size() == k){
            res.add((List<Integer>)c.clone());
            return;
        }

        // 还有k - c.size()个空位, 所以, [i...n] 中至少要有 k - c.size() 个元素
        // i最多为 n - (k - c.size()) + 1
        for(int i = start ; i <= n - (k - c.size()) + 1 ; i ++){
            c.addLast(i);
            generateCombinations(n, k, i + 1, c);
            c.removeLast();
        }

        return;
    }

更多的剪枝操作

斐波那契数列，发现递归树中会有很多重复的操作，通过设置一个数组判断时候计算过如果计算过则直接跳过计算直接返回数组中的值，只用计算一次。

public int fib(int n){

        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return fib(n, memo);
    }

    private int fib(int n, int[] memo){

        num ++;

        if(n == 0)
            return 0;

        if(n == 1)
            return 1;

        if(memo[n] == -1)
            memo[n] = fib(n - 1, memo) + fib(n - 2, memo);

        return memo[n];
    }

一个楼梯与n阶台阶，每一次只能上一个台阶或者上两个台阶，问爬一个楼梯一共有多少个方法。

总楼梯个数是一定的，每次都会减少1步或者减少两步，如果最后剩余的台阶个数为1的话，只剩下一种方法，如果剩下台阶个数为2会有两种方式，如果一个台阶都没有只有一种可能性一个都不走，因为当只剩2个台阶之后可以走一个台阶后再走一个台阶，或者是一个台阶都不走再走两个台阶。

private int[] memo;

    public int climbStairs(int n) {
        memo = new int[n+1];
        Arrays.fill(memo, -1);
        return calcWays(n);
    }

    private int calcWays(int n){

        if(n == 0 || n == 1)
            return 1;

        if(memo[n] == -1)
            memo[n] = calcWays(n - 1) + calcWays(n - 2);

        return memo[n];
    }

给定正数n，将其分隔成多个数字，数字乘积最大求分隔的方法。

递归树结构，从1开始把数字分隔为两个数字的乘积，剩余数字同样也可以分隔为其他最大数的乘积进行比较，递归终止的条件如果是1的话就没法再分隔了。

private int[] memo;

    public int integerBreak(int n) {

        if(n < 1)
            throw new IllegalArgumentException("n should be greater than zero");

        memo = new int[n+1];
        Arrays.fill(memo, -1);

        return breakInteger(n);
    }

    // 将n进行分割(至少分割两部分), 可以获得的最大乘积
    private int breakInteger(int n){

        if(n == 1)
            return 1;

        if(memo[n] != -1)
            return memo[n];

        int res = -1;
        for(int i = 1 ; i <= n - 1 ; i ++)
            res = max3(res, i * (n - i) , i * breakInteger(n - i));
        memo[n] = res;
        return res;
    }

    private int max3(int a, int b, int c){
        return Math.max(a, Math.max(b, c));
    }

一个背包的容量为C，n个物品重量为w价值为v，背包中放那些物品总价值最大。

形成的递归树结构，当前背包中有没有index物品的价值不影响背包的总价值与在背包容量的范围内加入index的物品价值最大两种可能性。

index与C形成一个数据对，有可能一个数据对计算了多次可以对背包进行记忆化搜索进行剪枝，背包被两个约束条件限制所以可以定义一个二维数组进行记忆化搜索。

int n = w.length;
        if(n == 0 || C == 0)
            return 0;

        memo = new int[n][C + 1];
        for(int i = 0; i < n; i ++)
            for(int j = 0; j <= C; j ++)
                memo[i][j] = -1;
        return bestValue(w, v, n - 1, C);
    }

    // 用 [0...index]的物品,填充容积为c的背包的最大价值
    private int bestValue(int[] w, int[] v, int index, int c){

        if(c <= 0 || index < 0)
            return 0;

        if(memo[index][c] != -1)
            return memo[index][c];

        int res = bestValue(w, v, index-1, c);
        if(c >= w[index])
            res = Math.max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));

        return memo[index][c] = res;
    }

给定一个数组数组中元素全是正整数，是否可以分割两部分使得两部分数字和相等。

一时间如果没有办法找到递归树结构，可以先转换为类型的其他问题，通过题目的条件以及其他的信息。

为了减少计算的次数首先要有一个达到的标准，把所有物品的价值计算出来为sum，只要和为sum/2即找到数组中是否存在两种组合和尾sum/2。计算每一种组合的值，然后判断是否等于sum/2。

判断是否和为sum/2有两种策略使用索引为index的数据才能把背包填满，不适用索引为index的数据同样也可以把背包填满。

// memo[i][c] 表示使用索引为[0...i]的这些元素,是否可以完全填充一个容量为c的背包
    // -1 表示为未计算; 0 表示不可以填充; 1 表示可以填充
    private int[][] memo;

    public boolean canPartition(int[] nums) {

        int sum = 0;
        for(int i = 0 ; i < nums.length ; i ++){
            if(nums[i] <= 0)
                throw new IllegalArgumentException("numbers in nums must be greater than zero.");
            sum += nums[i];
        }

        if(sum % 2 == 1)
            return false;

        memo = new int[nums.length][sum / 2 + 1];
        for(int i = 0 ; i < nums.length ; i ++)
            Arrays.fill(memo[i], -1);
        return tryPartition(nums, nums.length - 1, sum / 2);
    }

    // 使用nums[0...index], 是否可以完全填充一个容量为sum的背包
    private boolean tryPartition(int[] nums, int index, int sum){

        if(sum == 0)
            return true;

        if(sum < 0 || index < 0)
            return false;

        if(memo[index][sum] != -1)
            return memo[index][sum] == 1;

        memo[index][sum] = (tryPartition(nums, index - 1, sum) ||
                tryPartition(nums, index - 1, sum - nums[index])) ? 1 : 0;

        return memo[index][sum] == 1;
    }

复杂条件下的递归问题

一个街的所有房子，每个房子都有不同价值的宝物，不能连续拿两个房价，最多能获得多少价值的物品。

递归树结构不能有相邻的房间，检查每一个组合的价值，并判断是否有相邻的房子在数组中要去除。

// memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
    private int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return tryRob(nums, 0);
    }

    // 考虑抢劫nums[index...nums.size())这个范围的所有房子
    private int tryRob(int[] nums, int index){

        if(index >= nums.length)
            return 0;

        if(memo[index] != -1)
            return memo[index];

        // 或者当前房子放弃, 从下一个房子开始考虑
        // 或者抢劫当前的房子, 从i+2以后的房子开始考虑
        return memo[index] =
                Math.max(tryRob(nums, index + 1),
                         nums[index] + tryRob(nums, index + 2));
    }

给定一个子序列求最长上升子序列

递归树结构，从数组选择一个数字，然后判断以这个数字为结尾的判断后面的数字是否比前面的大，如果要大的话在前面已经统计的基础上自身多加一个一。

private int[] memo;

    public int lengthOfLIS(int[] nums) {

        if(nums.length == 0)
            return 0;

        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        int res = 1;
        for(int i = 0 ; i < nums.length ; i ++)
            res = Math.max(res, getMaxLength(nums, i));

        return res;
    }

    // 以 nums[index] 为结尾的最长上升子序列的长度
    private int getMaxLength(int[] nums, int index){

        if(memo[index] != -1)
            return memo[index];

        int res = 1;
        for(int i = 0 ; i <= index-1 ; i ++)
            if(nums[index] > nums[i])
                res = Math.max(res, 1 + getMaxLength(nums, i));

        return memo[index] = res;
    }

二维平面中的也可以形成树形递归结构，二维平面递归的小技巧

给定二维平面的字母和一个单词是否可以在二维平面中找到这个单词。

需要双重for循环把二维平面内的每一个点当做一个出发点，然后从上下左右四个方向去寻找，递归进行的条件就是遍历的深度也是字母索引位置index+1，索引到单词最后的位置递归结束。如果到达新的坐标是要找的字母则继续下去，否则回溯再从别的方向判断。

递归因为会返回到同一个位置无限执行下去形成死循环所以要加标识符，如果不满足回溯的时候要把标识符重置，下一次有可能从其他的方向过来也能形成单词。原先占用这个位置如果不能寻找到就要释放这个位置给其他情况使用。

d代表着往上、右、下、左四个方向移动

private int d[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private int m, n;
    private boolean[][] visited;

    public boolean exist(char[][] board, String word) {

        if(board == null || word == null)
            throw new IllegalArgumentException("board or word can not be null!");

        m = board.length;
        if(m == 0)
            throw new IllegalArgumentException("board can not be empty.");
        n = board[0].length;
        if(n == 0)
            throw new IllegalArgumentException("board can not be empty.");

        visited = new boolean[m][n];
        for(int i = 0 ; i < m ; i ++)
            for(int j = 0 ; j < n ; j ++)
                if(searchWord(board, word, 0, i, j))
                    return true;

        return false;
    }

    private boolean inArea( int x , int y ){
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    // 从board[startx][starty]开始, 寻找word[index...word.size())
    private boolean searchWord(char[][] board, String word, int index,
                               int startx, int starty){

        //assert(inArea(startx,starty));
        if(index == word.length() - 1)
            return board[startx][starty] == word.charAt(index);

        if(board[startx][starty] == word.charAt(index)){
            visited[startx][starty] = true;
            // 从startx, starty出发,向四个方向寻
            for(int i = 0 ; i < 4 ; i ++){
                int newx = startx + d[i][0];
                int newy = starty + d[i][1];
                if(inArea(newx, newy) && !visited[newx][newy] &&
                        searchWord(board, word, index + 1, newx, newy))
                    return true;
            }
            visited[startx][starty] = false;
        }
        return false;
    }

给二维数组，值包含0，1两个字符，0代表水，1代表陆地，横向纵向陆地连接代表岛屿问一共有多少个岛屿

也是求连通分量的问题，双重for循环，如果没有访问过则出发进行递归的遍历，一次递归说明形成了一个岛屿。

private int d[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;
    private boolean visited[][];

    public int numIslands(char[][] grid) {

        if(grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;

        m = grid.length;
        n = grid[0].length;

        visited = new boolean[m][n];

        int res = 0;
        for(int i = 0 ; i < m ; i ++)
            for(int j = 0 ; j < n ; j ++)
                if(grid[i][j] == '1' && !visited[i][j]){
                    dfs(grid, i, j);
                    res ++;
                }

        return res;
    }

    // 从grid[x][y]的位置开始,进行floodfill
    // 保证(x,y)合法,且grid[x][y]是没有被访问过的陆地
    private void dfs(char[][] grid, int x, int y){

        //assert(inArea(x,y));
        visited[x][y] = true;
        for(int i = 0; i < 4; i ++){
            int newx = x + d[i][0];
            int newy = y + d[i][1];
            if(inArea(newx, newy) && !visited[newx][newy] && grid[newx][newy] == '1')
                dfs(grid, newx, newy);
        }

        return;
    }

    private boolean inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }

复杂条件下的二维平面的递归

n*n的棋盘中横向和纵向以及两个对角线方向均不能同时出现两个皇后，求所有的解。

也是递归回溯的问题，从第一行出发选定一个位置，剩下的行数依次判断如果不满足要求则返回从第一行的其他位置出发继续寻找。最后回溯不从开始选定的位置出发，从其他的位置出发for循环形成所要的答案。

但是横纵还有对角线怎么进行判断条件，可以通过数组来判断，col代表第几列被占用，某个方向的对角线一共有2n-1个，根据坐标某个方向对角线上的所有坐标的横纵坐标之和是定值i+j，另一个方向的对角线相减的值为定制来确定哪一个对角线，数组的索引从0开始所以加上一个值。

ArrayList<List<String>> res = new ArrayList<List<String>>();
        col = new boolean[n];
        dia1 = new boolean[2 * n - 1];
        dia2 = new boolean[2 * n - 1];

        LinkedList<Integer> row = new LinkedList<Integer>();
        putQueen(n, 0, row);

        return res;
    }

    // 尝试在一个n皇后问题中, 摆放第index行的皇后位置
    private void putQueen(int n, int index, LinkedList<Integer> row){

        if(index == n){
            res.add(generateBoard(n, row));
            return;
        }

        for(int i = 0 ; i < n ; i ++)
            // 尝试将第index行的皇后摆放在第i列
            if(!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]){
                row.addLast(i);
                col[i] = true;
                dia1[index + i] = true;
                dia2[index - i + n - 1] = true;
                putQueen(n, index + 1, row);
                col[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
                row.removeLast();
            }

        return;
    }

    private List<String> generateBoard(int n, LinkedList<Integer> row){

        assert row.size() == n;

        ArrayList<String> board = new ArrayList<String>();
        for(int i = 0 ; i < n ; i ++){
            char[] charArray = new char[n];
            Arrays.fill(charArray, '.');
            charArray[row.get(i)] = 'Q';
            board.add(new String(charArray));
        }
        return board;
    }

图论中的递归算法

图的深度优先遍历求连通分量，遍历图中的所有节点从一个未被访问过的节点出发访问与它相邻的所有节点并进行标识，一轮递归循环下来就是一个连通分量

Graph G;                    // 图的引用
    private boolean[] visited;  // 记录dfs的过程中节点是否被访问
    private int ccount;         // 记录联通分量个数
    private int[] id;           // 每个节点所对应的联通分量标记

    // 图的深度优先遍历
    void dfs( int v ){

        visited[v] = true;
        id[v] = ccount;

        for( int i: G.adj(v) ){
            if( !visited[i] )
                dfs(i);
        }
    }

    // 构造函数, 求出无权图的联通分量
    public Components(Graph graph){

        // 算法初始化
        G = graph;
        visited = new boolean[G.V()];
        id = new int[G.V()];
        ccount = 0;
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            id[i] = -1;
        }

        // 求图的联通分量
        for( int i = 0 ; i < G.V() ; i ++ )
            if( !visited[i] ){
                dfs(i);
                ccount ++;
            }
    }

    // 返回图的联通分量个数
    int count(){
        return ccount;
    }

    // 查询点v和点w是否联通
    boolean isConnected( int v , int w ){
        assert v >= 0 && v < G.V();
        assert w >= 0 && w < G.V();
        return id[v] == id[w];
    }

获取从s为起点的一条路径

定义一个form数组来表示某个节点是从从哪一个节点过来的，最后返回路径需要栈来倒推出从哪个点过来的，直到回到原点。因为原点没有从其他店过来所以保持初始化为-1。

import java.util.Vector;
import java.util.Stack;

public class Path {

    private Graph G;   // 图的引用
    private int s;     // 起始点
    private boolean[] visited;  // 记录dfs的过程中节点是否被访问
    private int[] from;         // 记录路径, from[i]表示查找的路径上i的上一个节点

    // 图的深度优先遍历
    private void dfs( int v ){
        visited[v] = true;
        for( int i : G.adj(v) )
            if( !visited[i] ){
                from[i] = v;
                dfs(i);
            }
    }

    // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
    public Path(Graph graph, int s){

        // 算法初始化
        G = graph;
        assert s >= 0 && s < G.V();

        visited = new boolean[G.V()];
        from = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
        }
        this.s = s;

        // 寻路算法
        dfs(s);
    }

    // 查询从s点到w点是否有路径
    boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];
    }

    // 查询从s点到w点的路径, 存放在vec中
    Vector<Integer> path(int w){

        assert hasPath(w) ;

        Stack<Integer> s = new Stack<Integer>();
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        Vector<Integer> res = new Vector<Integer>();
        while( !s.empty() )
            res.add( s.pop() );

        return res;
    }

    // 打印出从s点到w点的路径
    void showPath(int w){

        assert hasPath(w) ;

        Vector<Integer> vec = path(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }
}