递归与回溯

关于递归与回溯

其实之前我们已经遇到了好多的递归的问题了，比如说动态规划里面的就用到了不少的递归，那种递归也可以转换成为递推。但是这里我们讲的是递归与回溯。何为回溯？

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

可以看出来递归其实是回溯的一个实现条件，一个算法既然和递归联系起来了，那免不了麻烦的事情，回溯法也是如此，需要我们对递归有着深层次的理解，才能够游刃有余的掌握。

看一下网上对回溯法的一些说明：

回溯法一般都用在要给出多个可以实现最终条件的解的最终形式。回溯法要求对解要添加一些约束条件。总的来说，如果要解决一个回溯法的问题，通常要确定三个元素：

选择。对于每个特定的解，肯定是由一步步构建而来的，而每一步怎么构建，肯定都是有限个选择，要怎么选择，这个要知道；同时，在编程时候要定下，优先或合法的每一步选择的顺序，一般是通过多个if或者for循环来排列。
条件。对于每个特定的解的某一步，他必然要符合某个解要求符合的条件，如果不符合条件，就要回溯，其实回溯也就是递归调用的返回。
结束。当到达一个特定结束条件时候，就认为这个一步步构建的解是符合要求的解了。把解存下来或者打印出来。对于这一步来说，有时候也可以另外写一个issolution函数来进行判断。注意，当到达第三步后，有时候还需要构建一个数据结构，把符合要求的解存起来，便于当得到所有解后，把解空间输出来。这个数据结构必须是全局的，作为参数之一传递给递归函数。

对于回溯法来说，每次递归调用，很重要的一点是把每次递归的不同信息传递给递归调用的函数。而这里最重要的要传递给递归调用函数的信息，就是把上一步做过的某些事情的这个选择排除，避免重复和无限递归。另外还有一个信息必须传递给递归函数，就是进行了每一步选择后，暂时还没构成完整的解，这个时候前面所有选择的汇总也要传递进去。而且一般情况下，都是能从传递给递归函数的参数处，得到结束条件的。

递归函数的参数的选择，要遵循四个原则：
1、必须要有一个临时变量(可以就直接传递一个字面量或者常量进去)传递不完整的解，因为每一步选择后，暂时还没构成完整的解，这个时候这个选择的不完整解，也要想办法传递给递归函数。也就是，把每次递归的不同情况传递给递归调用的函数。
2、可以有一个全局变量，用来存储完整的每个解，一般是个集合容器（也不一定要有这样一个变量，因为每次符合结束条件，不完整解就是完整解了，直接打印即可）。
3、最重要的一点，一定要在参数设计中，可以得到结束条件。一个选择是可以传递一个量n，也许是数组的长度，也许是数量，等等。

4、要保证递归函数返回后，状态可以恢复到递归前，以此达到真正回溯。

递归与回溯的经典案列

迷宫问题

基本介绍

看到之前回溯的概念我们可以非常轻易的想到迷宫问题。走不通就退回再走的技术为回溯法，迷宫不也是走不通就退回再走吗，非常的符合回溯法的使用条件。

至于迷宫问题的题目我就不多说了，就以下面的数组为例，起始点假如规定在左上角的[1][1]处，目标终点在右下角的[10][25]，请走迷宫，并显示程序所走的路径。下图中0表示路，1表示墙。**

map = new int[][] {
    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
    {1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,1},
    {1,1,1,1,0,1,0,0,1,1,0,1,1,0,0,0,0,0,1,1,0,1,0,1,1,0,1},
    {1,1,0,0,0,1,1,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,0,0,0,0,1},
    {1,1,1,1,0,1,0,0,0,1,0,0,0,1,1,1,1,0,1,1,0,1,1,1,1,1,1},
    {1,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,1,0,0,1},
    {1,0,0,1,0,0,0,1,0,1,0,1,1,1,0,1,1,0,0,0,0,1,0,1,1,0,1},
    {1,0,1,1,1,1,1,1,0,1,0,1,1,0,1,1,1,0,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,0,0,1,1,1,1,1,1,0,1},
    {1,1,0,1,1,1,1,1,1,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,1},
    {1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0,1},
    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
};

思路分析

我们很容易想到回溯但是到底如何回溯呢？我们要告诉程序如何去走这个迷宫，第一点就是，当四条路都可以走的时候我们怎么走？这是最关键的，我们要给程序设定一个初识的目标，遇到多路口先走什么。

  0
0 x 0
  0

这时我们可以规定一个策略就是先走右面，如果右面不通再走下面，如果再不通就走上面，如果还是不通就走上面。

使用→↓←↑的策略进行这一场的迷宫游戏。

那么有没有可能出现这样一种情况，四条路都不通。——怎么可能四条路都不通，四条路都不通你是怎么进来的？？？

唉~你错了，还真的有四条路都不通的情况，比如如下的图。

不对啊，这条路上面不是通的吗？往上走不就完事了吗？但是我们是就是从上面下来的，还能再回到上面去吗？所以我们有必要把我们走过的路进行标记比如标记为2。如果走路的这个路确定是死路了，我们还可以将他标记为3，以和我们走过的路正确的路径进行区分。如果四周都是墙或者走过的路，那么这条路的递归就结束，回到选择这个递归的那个路口，开始下一条路的递归。这就是回溯的过程这样说可能很难听懂，不过看到了代码可就算是柳暗花明了。

代码实现

处于路口(迷宫的某一个点)时找路的代码

// 递归与回溯
private boolean findWay(int i, int j) {
    //        count++;
    // 只有走到了目标终点的位置这个函数才会返回true
    if (map[map.length - 2][map[0].length - 2] == 2) {
        return true;
    } else {
        // == 0 代表这条路还没有走过
        if (map[i][j] == 0) {
            // 设为2 假定这条路可以走了
            map[i][j] = 2;
            // 找路的策略是：
            // 向下 -》 向右 -》 向上 -》 向左
            if (findWay(i + 1, j)) {
                return true;
            } else if (findWay(i, j + 1)) {
                return true;
            } else if (findWay(i - 1, j)) {
                return true;
            } else if (findWay(i, j - 1)) {
                return true;
            } else { // 四条路都走不通了
                map[i][j] = 3;
                return false;
            }
        } else { // 不是0可能是 1 2 3，反正就是不能走这条路
            return false;
        }
    }
}

代码说明：
这个函数的返回值是什么意思？

函数的返回值是boolean，他只有在一个情况上返回的是true，那就是走到了目标终点了。虽然下面也有几个return true，但是那些return true都是依靠if里面为真，而if里面为真只是依靠找到终点了。

下面的if为0是什么意思？

让我们找路给我们的坐标是i，j如果给定的就是一堵墙，走过了的或者死路，当然要返回false，让它进行下一个路口的探索。也就是下右上左的次序进行走路（其实什么顺序都可以啦，没什么太重要的，都可以走到终点的）。

最后的那个else returnfalse是？

这说明前面的四个递归返回的都是false，说明什么？四条路都是走不通的，那么就把这个点置为死路点，标记为3。
那这个不是只有一个点是3吗？？死路就这是一个点？

不是的，当这个点被置为死路3的时候，递归会回溯。比如下面的这个路。
1 2 1
1 3 1
1 1 1
（1,1）被标记为3之后，可别忘了(1,1)点是从(0,1)点走过来的。走路的顺序是下右上左。(0,1)点的下面返回false，于是走右面，不通，走上面，走过了，走左面，不通，于是(0,1)也被置为了3。

所以说被置为3的是通往死路的那一整条路啦~~递归就是这么神奇。

这个findWay函数写完了，直接调用findWay(1,1)就可以进行迷宫的探索了。（我们规定的是1,1是起点了）

迷宫的输出结果

==================Maze Result========================
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# X X X X #         X X X X     # #           # #   # 
# # # # X #     # # X # # X X X X X # #   #   # #   # 
# #     X # # # # # X # # N # # # X # #   #         # 
# # # # X # X X X # X X X # # # # X # #   # # # # # # 
#     # X # X # X # X X X N N # # X # #   #   #     # 
#     # X X X # X # X # # # N # # X       #   # #   # 
#   # # # # # # X # X # #   # # # X   # # #         # 
#   X X X X X X X # X # #   # # # X   # # # # # #   # 
# # X # # # # # # X X # #   # #   X X X X X X X X X # 
# # X X X X X X X X # # #         # # # # # # # # X # 
# # # # # # # # # # # # # # # # # # # # # # # # # # #

这里我们使用#表示墙，X表示正确的路径，N表示走过的死路。空白的区域就是没有走过的路。可见这个下右上左的策略还是蛮不错的，走过的死路是比较上的。如果我们换成左上右下，那么结果又是如何呢？

==================Maze Result========================
# # # # # # # # # # # # # # # # # # # # # # # # # # # 
# X X X X # N N N N X X X X X X # # N N N N N # # N # 
# # # # X # N N # # X # # N N X X X # # N # N # # N # 
# # N N X # # # # # X # # N # # # X # # N # N N N N # 
# # # # X # X X X # X     # # # # X # # N # # # # # # 
# N N # X # X # X # X         # # X # # N # N # N N # 
# N N # X X X # X # X # # #   # # X X N N # N # # N # 
# N # # # # # # X # X # # N # # # X X # # # N N N N # 
# N X X X X X X X # X # # N # # # X X # # # # # # N # 
# # X # # # # # # X X # # N # # N N X X X X X X X X # 
# # X X X X X X X X # # # N N N N # # # # # # # # X # 
# # # # # # # # # # # # # # # # # # # # # # # # # # #

可以看出走过的死路是非常多的，但是无论怎么说都是可以到达终点的。毕竟我们这个题目是从左上角到右上角，我们选定的策略肯定是选右下啊。

在不知道起点终点的时候，我们可以四个策略都使用一下，看看哪个策略走的次数是最少的（有效的路，不算死路)。前面我的代码中也使用了count来计数，就是为了这一点。这样我们基本就可以确定走迷宫的最优路径了。

八皇后问题

基本介绍

这个题目可以说是非常著名了，我学python的时候就在研究这个问题，但是当时怎么研究都研究不出来到底怎么解决这个问题。递归这种事我们都是不敢想的（递归那该有多难啊），回溯根本不知道回溯是什么玩意。不过现在有个递归和回溯这个武器，八皇后问题可以说只用几行代码就完事了。看一下百度百科对八皇后问题的解释

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

现在有个计算机，什么八皇后，就是八十皇后都么得问题。

思路分析

上面也说了，八皇后问题同样是回溯算法的典型案列。那么这个问题该如何回溯呢？迷宫问题是路走不通了我退回去重新走其他的路，那八皇后也很好理解了。皇后放不了了，我换其他地方重新放。

我们可以选择一行一行的放置皇后，这个显然不会对结果产生什么影响，你要是乐意一列一列放也是可以的。

大多数人解决这个问题都喜欢使用二维数组，第一个表示行，第二个表示列，数组的值表示有没有放置过皇后，我承认这样可行。但是真的有必要使用二维数组吗？我们使用一维数组不可以解决这个问题吗？比如使用一个一维数组int[8]。int[0]表示第一行皇后所在的列，我们只要按顺序去放置int[1],int[2]里的值就完事了，这不是很好喵~

下面就该说说八皇后的回溯了。首先我们也要和迷宫一样确定如何放置皇后，这里其实很容易，直接从第一列开始依次往后尝试呗。（这也是正常人的思想）如果某一列不可以放置皇后(要写个函数进行判断)，就往后放，如果已经是最后一列了。就直接返回false。回到上面的一行(回溯算法)，重新按顺序放置皇后。如果可以放置，就进入下面一行放置皇后，如果第八行的皇后都放置OK了就返回true，这是一种皇后的放置方法已经完成了，不过我们需要循环找到所有的皇后的放置的方法。

代码实现

判断是否可以放置皇后

private boolean isValid(int n) {
    ++count2;
    for (int i = 0; i < n; i++) {
        // 在同一列或者说是在同一个斜线上
        if (map[i] == map[n] || Math.abs(map[n] - map[i]) == Math.abs(n - i)) {
            return false;
        }
    }
    return true;
}

代码说明：

count2++

这个是后面用来统计进行了多少次的皇后判断用的。

map[i] == map[n]?

我们说过了一维数组的值表示的是皇后所在的列，如果map[i] == map[n]那么就说明放置的皇后在同一列，返回的false。

Math.abs(map[n] - map[i]) == Math.abs(n - i)?

这个代表的意义就是列差的绝对值是等于行差的绝对值的。这个我都是使用斜率来理解的。斜率为1或者-1，那么两个皇后就是在一天斜线上！斜率为其他值的就不算一天直线了吧，国际象棋的规则明白吧老弟~

这里我们只是和n前面那的皇后进行比较，那么后面呢？

后面个锤子啊，我们放置皇后的顺序是从第一列一次到第八列，后面的皇后还都没有放呢，当然不用来比较。

在某一行开始放置皇后

private void check(int n) {
    if (n == max) {
        // 输出解决方案
        System.out.printf("%-3d" + ": " + Arrays.toString(map) + "\n", ++count);
        return;
    }

    for (int i = 0; i < map.length; i++) {
        map[n] = i;
        if (isValid(n)) {
            check(n + 1);
        }
    }
}

代码说明：

我只知道System.out.println，那个printf是什么鬼？

没学过c吗？printf是Java中用于格式化输出的语句，%-3d的意思就是三位数的整数，左对齐。

后面的for循环是？？？

如果不加上for循环的话我们啥都得不到，而且肯定是前面几个皇后的列值都很小的。比如说没有for循环的时候我们使用check(0)就是放置第一个皇后，第一个皇后置为i(一开始也就是0，因为没有for循环)，然后看在i处放置合不合理。如果合理就开始放置下面一个皇后，但是倘若是不合理呢？？不合理是不是直接就没了，程序也不会尝试其他的路径了。

如果加上这个for循环。合理自然很好，一路往下走。假如遇到了不合理的。（就算是合理的也会往后的）那for循环就会执行给我们尝试后面的列是否可行。如果for循环结束了都是不可行的。那么这一层的递归就结束了。就会返回上一层的递归。（就算这个合理了也是会返回上一层的递归的），在上一层寻找其他的放置皇后合理的地方。就这样一直回溯就可以找到八皇后的所有的解了。递归是真的神奇~~比如之前一直都不理解的归并排序。

测试代码

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.print("Slove N Queue Problem: ");
    int num = scanner.nextInt();
    Queue8 queue8 = new Queue8(num);
    System.out.println("=====THE SOLUTION OF " + num + "QUEUE PROBLEM=====");
    long start_time = System.currentTimeMillis();
    queue8.check(0);
    long end_time = System.currentTimeMillis();
    System.out.println();
    System.out.println("=====================SUMMARY=====================");
    System.out.println("THE NUMBERS OF " + num + "QUEUE SOLUTIONS IS " + count);
    System.out.println("THE NUMBERS OF JUDGES IS " + count2);
    long time = end_time - start_time;
    System.out.println("THE TIME USED IS " + time + "MS");
}

8皇后

=====================SUMMARY=====================
THE NUMBERS OF 8QUEUE SOLUTIONS IS 92
THE NUMBERS OF JUDGES IS 15720
THE TIME USED IS 1MS

这里的解决方案没有输出，因为太长了，顶不住啊。由此可见是92种，看来天才高斯也有错误的时候啊~~嘤嘤嘤

12皇后

=====================SUMMARY=====================
THE NUMBERS OF 12QUEUE SOLUTIONS IS 14200
THE NUMBERS OF JUDGES IS 10103868
THE TIME USED IS 154MS

20皇后

.....
等了好长的时间（20秒）都没有输出，这个判断函数执行的次数我感觉肯定有上百亿次。。。估计我再不退出就可能
会发生栈溢出了。。。还是不等这个输出结果了吧。

上面的两个问题都是我亲手完成和研究的问题，不过递归和回溯算法的题目不止如此，下面看几个网上看到的几个题目。

括号排列

基本介绍

给出n对括号，求括号排列的所有可能性。

思路分析

对于回溯法来说，必须齐备的三要素：

1、选择。在这个例子中，解就是一个合法的括号组合形式，而选择无非是放入左括号，还是放入右括号；

2、条件。在这个例子中，选择是放入左括号，还是放入右括号，是有条件约束的，不是随便放的。而这个约束就是括号的数量。只有剩下的右括号比左括号多，才能放右括号。只有左括号数量大于0才能放入左括号。这里if的顺序会影响输出的顺序，但是不影响最终解；

3、结束。这里的结束条件很显然就是，左右括号都放完了。

回溯法中，参数的设计是一大难点，也是很重要的地方。而递归参数的设计要注意的四个点：

1、用了一个空字符串来作为临时变量存储不完整解；

2、用了一个ArrayList results来存放符合要求的解。在后面可以看到，不一定要这样做，也可以直接打印结果；

3、把leftnum和rightnum传入给递归函数，这样可以用于判断结束条件；

代码实现

import java.util.ArrayList;

public class BackTracking {
    public static void main(String[] args) {
        int n = 3;
        int leftnum = n, rightnum = n;// 左括号和右括号都各有n个
        ArrayList<String> results = new ArrayList<String>();// 用于存放解空间
        parentheses("", results, leftnum, rightnum);
        for (String s : results)
            System.out.println(s);
    }

    public static void parentheses(String sublist, ArrayList<String> results, int leftnum, int rightnum){
        if (leftnum == 0 && rightnum == 0)// 结束
            results.add(sublist);
        if (rightnum > leftnum)// 选择和条件。对于不同的if顺序，输出的结果顺序是不一样的，但是构成一样的解空间
            parentheses(sublist + ")", results, leftnum, rightnum - 1);
        if (leftnum > 0)
            parentheses(sublist + "(", results, leftnum - 1, rightnum);
    }
}

代码说明：
parentheses函数的参数的说明

@param sublist 尚未完成的括号串

@param results 存放已经完成的括号串的字符串

@param leftnum 左括号的数量

@param rightnum 右括号的数量
回溯算法如何实现的？

其实这个算法我倒是感觉没有什么回溯的味道，就是单纯的递归而已。当剩下的左括号和右括号的数量都为0的时候，就是一条递归终止，然后将结果放入集合中。

当剩下的右括号的数量比较多的时候（放入的左括号的数量大于放入的右括号的数量）此时就放入右括号。（如何剩下的右括号的数量小于等于左括号的数量放入右括号是非法的）

当还有剩下的左括号，就放入左括号。

这或许有点不好理解，下面的两个条件其实是在同步进行的。比如说
比如要放四个括号，遇到了这样的字符串 (()(
经过第二个条件的判断产生的递归的分支是 (()()
经过第三个条件的判断产生的递归的分支是 (()((
通过了上面的说明就可以理解，不存在少了哪一种情形。每一次的递归都是一种结果。不过，这个算法里面是真的没有回溯这个部分，只是递归而已。

不过作者偏说这个有回溯的部分。

4、这个例子不明显。但是事实上也符合这个条件。可以仔细观察代码，可以发现由于使用了两个if，所以当一次递归退出后，例如从第一个if退出，第二个递归直接递归的是leftnum-1和rightnum，这其实是已经恢复状态了（如果没有恢复状态，那就是leftnum, rightnum-1）。因此不需要人为让他恢复状态。但是恢复状态这点是很重要的，因为回溯法，顾名思义要回溯，不恢复状态，怎么回溯呢。

if(rightnum>leftnum)//选择和条件。对于不同的if顺序，输出的结果顺序是不一样的，但是构成一样的解空间
    parentheses(sublist+")", results, leftnum, rightnum-1);
if(leftnum>0)
    parentheses(sublist+"(", results, leftnum-1, rightnum);

把这个称为是回溯，确实是有点儿牵强。每一个递归都是这样使用的不是吗？因为每一层递归不在一个栈空间，在同一个栈空间的数据当然是相同的，自然不用人为恢复状态。

数字之和

基本介绍

给出一个不重复大于0数字的数组和一个目标，求数组中数的组合的和得到该目标（数字不同组合顺序当做一个解）。

这个和leetcode上的第一题两数之和是有点儿像的，不过这个题目似乎是没有规定这些数的个数是2，那么难度就不是一倍两倍的往上涨了。两数之和可以使用排序双指针轻松解决，不过这个题目使用排序双指针似乎有点儿困难。

思路分析

代码实现


public class BackTracking {
    public static void main(String[] args){
        int[] num=new int[]{2,3,7,6，4,9,1};
        int target=9;
        find(num, target, "");
    }
    public static void find(int[] num, int target, String temp){
        if(issolution(temp,target)){
            System.out.println(temp);
            return;
        }
        for(int i=0;i<num.length;i++){
            if(num[i]!=-1){//如果取过这个数字了，就置为-1
                int k=num[i];
                num[i]=-1;
                find(num, target, temp+k);
                num[i]=k; // 恢复取出的数据的值。
            }
        }
}
    public static boolean issolution(String temp, int target){
        boolean result=false;
        int count=0;
        for(int i=0;i<temp.length();i++){
            count=count+Integer.valueOf(temp.charAt(i)+"");
        }
        if(count==target)
            result=true;
        return result;
    }
}

代码说明：

for循环里面？

其实这一整块的代码只有for循环的里面是需要说明的。首先先记录一下放入组合中的那个数据，然后将之置为0.然后再次递归，这样在那个递归的find里面数组的num[i]就为-1了。在后面将i再次恢复到-1从而不影响其他的递归空间。下面的那个issolution函数也非常的容易理解。

代码存在的问题

首先这个代码不是我写的，但是我再研究了多道递归的题目的时候还是看出了一个代码其实还是有不少的问题的。

首先我们看一下这个问题的输出如何：

不得不说这个结果的输出就是非常乱的，首先没有任何的分隔符告诉我是那些数的组合，其次，全是重复！！！这个算法其实就是暴力破解法，效率是特别的低的。可以改进的空间非常大！

首先输出得改善，第二得去重复，第三要考虑到效率问题。针对这三个点，我重写了这个代码。

重写代码

public class BackTracking2 {
    public static void main(String[] args) {
        int[] num = new int[] { 2, 3, 7, 6, 4, 9, 1};
        Arrays.sort(num);
        int target = 9;
//      find(num, 0, target, "");
        find(num, target);
    }

    public static void find(int[] num, int loc, int target, String temp) {
        int result = issolution(temp, target);
        if (result == 0) {
            System.out.println(temp);
            return;
        }
        if (result > 0) {
            // 和都已经大于target了， 再增加已经没有任何的意义了
            return;
        }
        for (int i = loc; i < num.length; i++) {
            if (num[i] <= target) {// 如果取过这个数字了，就置为-1
                find(num, i + 1, target, (temp + num[i]) + " ");
            } else {
                return;
            }
        }
    }

    // 可以重载一下，是调用更加简洁
    public static void find(int[] num, int target){
        find(num, 0, target, "");
    }

    public static int issolution(String temp, int target) {
        int count = 0;
        for (int i = 0; i < temp.length() / 2; i++) {
            count = count + Integer.valueOf(temp.charAt(2 * i) + "");
        }
        if (count > target)
            return 1;
        if (count < target)
            return -1;
        return 0;
    }
}

输出结果：

1 2 6
2 3 4
2 7
3 6
9

可见这个输出结果就是很舒服的

代码说明：

关于输出

输出添加了空格主要就是修改了上面的23,31,32这几行，这个修改起来相对简单容易理解。

关于重复

其实重复这个问题也蛮好解决的，只要好马不吃回头草就行了。你想想看比如2，3，7，6假如我挑选的是已经把所有的包含2的都挑选完了，那么在我挑选3的时候，为何还要继续挑选前面的2呢？我们只需要给函数加上一个参数loc，告诉他从什么位置开始挑选就可以完美地解决这个问题了。

关于效率

原先的真的是暴力算法，一点效率都没有。首先是作为自以为完美的将num[i]置为-1，然后再还原的操作，虽然说的确是很秀但是真的没有必要。还有issoluation函数的返回值，完美可以返回大于小于和等于，然后利用大于可以直接结束递归。还有就是将num数组进行排序，虽然说不排序也可以做，但是排序之后的效率将变得高的多，而且还可以在函数中利用num[i] > target就直接结束这个函数（num数组是递增的），可以说是提高了效率。

不过说修改之后的函数就没有问题了，这也是不可能的，我认为还是可以继续改进的，不过做到这一块已经可以说是基本上差不多了。

字符串排列

基本介绍

给一个字符串，给出他的所有排列

什么叫字符串的所有的排列呢？就比如说给定的字符串是abc，他的所有的排列就是

abc acb bac bca cab cba

总共有 A³₃ = 3! = 3 × 2 × 1= 6 种

思路分析

这个其实也是一种放东西类型的题目，和上面的那一个题目倒是有一点儿类似，不对，应该说是有点儿儿完全一样，就是上面的那一个题目改进前的那个算法。毕竟这玩意是需要重复的嘛。

代码实现

public class StringArrange {
    public static void main(String[] args) {
        String s = "abc";
        Arrange(s, "");
    }

    public static void Arrange(String s, String temp) {// 参数设计地尽量地简洁
        if (s.length() == 0) {
            System.out.println(temp);
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            String news = s.substring(0, i) + s.substring(i + 1, s.length());// 去掉String中的某个字母
            Arrange(news, temp + s.charAt(i));
        }
    }
}

// 既然你要说参数设计要简洁的话为啥不给这个函数一个重载呢？
public static void Arrange(String s){
    Arrange(s, "");
}
// 然后直接这样子调用不就完事了
String s = "abc";
Arrange(s);

输出结果：

abc
acb
bac
bca
cab
cba

代码说明：

这个其实没有什么要说明的地方，不过要注意的一点是java当中substring的第二个参数是结束的位置（不包括），C++中的substr()的第二个参数是子串的长度。关于这一点，我也算是佛了！

还有一个与之比较类似的题目。

新字符串

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

这个题目可以直接用前面的回溯算法，而且真的特别的简单，至于效率，应该不是很快吧。不过真的是特别容易理解。

代码实现

public class NewStr {
    public static void main(String[] args) {
        String a = "ak47A";
  //    newStr(a, 0, "");
        newStr(a);
    }

    public static void newStr(String a, int i, String temp) {
        if (i == a.length()) {
            System.out.println(temp);
            return;
        }

        if (Character.isAlphabetic(a.charAt(i))) {
            String temp2 = new String(temp);
            temp += a.charAt(i);
            newStr(a, i+1, temp);
            if (Character.isLowerCase(a.charAt(i))) {
                temp2 += Character.toUpperCase(a.charAt(i));
            }else {
                temp2 += Character.toLowerCase(a.charAt(i));
            }
            newStr(a, i+1, temp2);
        }else {
            temp += a.charAt(i);
            newStr(a, i+1, temp);
        }
    }

    public static void newStr(String a){
        newStr(a, 0, "");
    }
}

输出结果：

ak47A
ak47a
aK47A
aK47a
Ak47A
Ak47a
AK47A
AK47a

代码说明：

这个代码实在是太容易理解了，不用说什么了。里面用到了几个库函数，看函数的名字大概就可以知道函数的意思了。

我看到博主使用的代码有点沙雕，不过思路是完全一样子的（我可没有看这个函数起名都花里胡哨的代码，dfs。。。to784To？？？我佛了）。这里就直接说我上面的那个算法就完事了，至于博主的算法直接贴出来就完事了。

public void dfs(String pre, String S, List<String> res, int index) {
    if (index == S.length())
        res.add(pre);
    else {
        char ch = S.charAt(index);
        if (!Character.isLetter(ch))
            dfs(pre + ch, S, res, index + 1);
        else {
            // 小写字符分支
            ch = Character.toLowerCase(ch);
            dfs(pre + ch, S, res, index + 1);
            // 大写字符分支
            ch = Character.toUpperCase(ch);
            dfs(pre + ch, S, res, index + 1);
        }
    }
}

public List<String> letterCasePermutation(String S) {
    List<String> res = new LinkedList<>();
    dfs("", S, res, 0);
    return res;
}

// 测试
public static void main(String[] args) {
    String S = "a1b";
    To784To to784To = new To784To();
    System.out.println(to784To.letterCasePermutation(S));
}

子集问题

给定一个集合，求他的所有的子集

就不上什么思路分析了，直接代码

代码实现

public class Subsets {
    public static List<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

    public static List<ArrayList<Integer>> subsets(int[] arr) {
        ArrayList<Integer> curr = new ArrayList<Integer>();
        subsets(arr, curr, 0);

        // System.out.println(res);
        return res;
    }

    public static void subsets(int[] arr, ArrayList<Integer> curr, int start) {
        res.add(new ArrayList<Integer>(curr)); // 如果不这样放，最后就都是空
        if (start == arr.length) {
            return;
        }
        for (int i = start; i < arr.length; i++) {
            curr.add(arr[i]);
            subsets(arr, curr, i + 1);
            curr.remove(curr.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3 };
        subsets(arr);
    }
}

要注意一点的是，放入res的时候，如果不new的话，放入的就是引用，（Java万物都是引用）最后就都会变成空的集合。这一点上C++和Java的区别要尤其的注意。这两门语言名义上说是很像，但是这点差的真的是特别的大。我也是佛了。

总结

递归与回溯确实有点儿难以掌握，刚才去leetcode上面看了一题，还是有点儿懵，虽然有了思路，但是并不能完全的写下去，唉，还是要多加的训练才能基本掌握这门高深的“通用解题方法”啊。

参考了一点的文章: 回溯算法超通俗易懂详尽分析和例题

递归与回溯

递归与回溯

关于递归与回溯

递归与回溯的经典案列

迷宫问题

基本介绍

思路分析

代码实现

处于路口(迷宫的某一个点)时找路的代码

迷宫的输出结果

八皇后问题

基本介绍

思路分析

代码实现

判断是否可以放置皇后

在某一行开始放置皇后

测试代码

括号排列

基本介绍

思路分析

代码实现

数字之和

基本介绍

思路分析

代码实现

代码存在的问题

重写代码

字符串排列

基本介绍

思路分析

代码实现

新字符串

代码实现

子集问题

代码实现

总结

Sunday字符串匹配算法

二叉树的广度优先和深度优先遍历

Hony Sher