转载

算法基础（Java）--回溯算法

本文还是转载加编写，关于算法的教程网上很多很多，找到这个比较适用的，算法本身就是一种思想，掌握了思想，再根据一些数学知识解决问题。

1. 什么是回溯算法？

回溯法是一种系统搜索问题 解空间 的方法。为了实现回溯，需要给问题定义一个 解空间 。说到底它是一种 搜索算法 。只是这里的搜索是在一个叫做 解空间 的地方搜索。而往往所谓的dfs，bfs都是在图或者树这种数据结构上的搜索。根据定义来看，要实现回溯，需要两点 1搜索 ， 2解空间 先看什么是 解空间 。就是形如数组的一个向量[a1,a2,....,an]。这个向量的每个元素都是问题的部分解，只有当这个数组的每一个元素都填满 (得到全部解)的时候，才表明这个问题得到了解答。再看搜索。最简单的就是for循环，上面的向量有n个维度，因此就是n个for循环。形如：

for(求a1位置上的解)
   for(求a2位置上的解)
      for(求a3位置上的解)
       ......
       ......
       for(求an位置上的解)
复制代码

但是如果n是100？n是100000？那么如何回溯？当然也可以写n个for循环，但是这样的程序会惨不忍睹。。。而且似乎10000个(不过往往回溯的时间复杂度太大，一般n不会这么大)for循环也很难写出来。。。因此我们需要一种全新的书写回溯的方法。形如：

void backtrack(int i,int n,other parameters)
{
  if( i == n)
{
 //get one answer
record answer;
return;
}
//下面的意思是求解空间第i个位置上的下一个解
for(next ans in position i of solution space)
{
  backtrack(i+1,n,other parameters);
}
}
复制代码

就是这么简单！！！上面的模板适用于所有"解空间确定"的回溯法的问题！！！上面的i代表解空间的第i个位置，往往从0开始，而n则代表解空间的大小。每一次的backtrack(i,n,other)调用,代表求 解空间 第i个位置上的解。而当i=n时，代表解空间上的所有位置的解都已经求出。有了上述模板，我们就解决了搜索的问题。因此几乎所有回溯的问题的难度都在于如何定义 解空间 。

2. 实例

下面通过题目，带入模板，然后再看我的解答，来感知一下如何定义解空间。

2.1全排列

即对没有重复数字的数组a=[a1,a2,a3,...an]求全排列。解空间定义为s=[s1,s2,s3,....sn]与数字长度相同。s的每一个元素s【i】(i >= 0&&i < n),都为数组a中的任意元素a【j】(j >= 0&&j < n)，不过要保证任意的s【i】不相等。这里唯一复杂的地方是需要用一个boolean【】数组来表明哪些数已经用过，这样才能保证任意的s【i】不相等。因此我们看到，回溯本身是很简单的，单纯的模板套用，难的在于需要根据回溯条件来定义各种别的变量，以及最后结果的记录。

2.2探测路径

(这个下面给出ac 代码) 这个题很难，但是掌握了如何定义解空间之后再做这个题就会感觉是小儿科了。这里的解空间s = [s1,s2,s3,....sn]中的每一个元素s【i】代表格子的坐标(x,y),因此从 逻辑上 来看，s应该是一个类类型的数组。不过，这个题求的是数目，而不是最后的确切路径，因此解空间在这里并没有记录。 java ac代码：

class Solution {
    int ans;
    public int uniquePathsIII(int[][] grid) {
        if(grid.length == 0)return 0;
        int num = 0;
        int x = 0,y = 0;
        for(int i = 0;i < grid.length;i++)
            for(int j = 0;j < grid[0].length;j++){
                if(grid[i][j] == 1||grid[i][j] == 0)num++;
                if(grid[i][j] == 1){x = i;y = j;}
            }
        backtrack(0,num,x,y,grid,new boolean[grid.length][grid[0].length]);
        return ans;
    }

    void backtrack(int i,int n,int x,int y,int[][]grid,boolean[][]flag)
    {
        if(!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)||flag[x][y]||grid[x][y] == -1)
            return;
        if(i == n && grid[x][y] == 2)
        {
            ans++;
            return;
        }
        flag[x][y] = true;
        backtrack(i+1,n,x+1,y,grid,flag);
        backtrack(i+1,n,x-1,y,grid,flag);
        backtrack(i+1,n,x,y+1,grid,flag);
        backtrack(i+1,n,x,y-1,grid,flag);
        flag[x][y] = false;
    }
}

复制代码

上面这个题的解空间应该有N+1维才对，但是为了方便书写，我只求出前n维位置的解，然后保证最后一维中位置是终点即可。

如果仍然觉得抽象，那么我建议大家把回溯想象成 “填格子” 游戏。到leetcode上找回溯的专题，对于每一个回溯法可解的问题，看看这题需要填的格子(格子就是解空间)是什么。

比如n个不重复字母的全排列，不就是填充n个格子，填满并且合法就得到一个解。

2.3括号生成

这里的格子的数量是 括号对数 乘以2，格子上填的就是左括号或者右括号，这里的剪枝条件是，当前右括号数量超过了左括号，或左括号数量超过了一半。当然为了剪枝需要在函数参数中维护左右括号数这两个变量。

思路和算法

只有在我们知道序列仍然保持有效时才添加 '(' or ')'，而不是像方法一那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，

如果我们还剩一个位置，我们可以开始放一个左括号。如果它不超过左括号的数量，我们可以放一个右括号。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, String cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }

        if (open < max)
            backtrack(ans, cur+"(", open+1, close, max);
        if (close < open)
            backtrack(ans, cur+")", open, close+1, max);
    }
}
复制代码

原文 https://juejin.im/post/5d6bd389e51d4561b674c4a6

正文到此结束