22-括号生成(回溯&深搜)

22. 括号生成

这一类问题是在一棵隐式的树上求解，可以用深度优先遍历，也可以用广度优先遍历。
一般用深度优先遍历。原因是：

代码好写，使用递归的方法，直接借助系统栈完成状态的转移；
广度优先遍历得自己编写结点类和借助队列。

这里的「状态」是指程序执行到隐式树的某个结点的语言描述，在程序中用不同的变量加以区分。

深度优先遍历

减法

画图以后，可以分析出的结论：

当前左右括号都有大于 0 个可以使用的时候，才产生分支；
产生左分支的时候，只看当前是否还有左括号可以使用；
产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；
在左边和右边剩余的括号数都等于 0 的时候结算。

public class Solution {

    // 做减法

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 特判
        if (n == 0) {
            return res;
        }

        // 执行深度优先遍历，搜索可能的结果
        dfs("", n, n, res);
        return res;
    }

    /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号还有几个可以使用
     * @param right  右括号还有几个可以使用
     * @param res    结果集
     */
    private void dfs(String curStr, int left, int right, List<String> res) {
        // 因为每一次尝试，都使用新的字符串变量，所以无需回溯
        // 在递归终止的时候，直接把它添加到结果集即可，注意与「力扣」第 46 题、第 39 题区分
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }

        // 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
        if (left > right) {
            return;
        }

        if (left > 0) {
            dfs(curStr + "(", left - 1, right, res);
        }

        if (right > 0) {
            dfs(curStr + ")", left, right - 1, res);
        }
    }
}

如果我们不用减法，使用加法，即 left 表示「左括号使用了几个」，right 表示「右括号使用了几个」，可以画出另一棵递归树。

public class Solution {

    // 做加法

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 特判
        if (n == 0) {
            return res;
        }

        dfs("", 0, 0, n, res);
        return res;
    }

    /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号已经用了几个
     * @param right  右括号已经用了几个
     * @param n      左括号、右括号一共得用几个
     * @param res    结果集
     */
    private void dfs(String curStr, int left, int right, int n, List<String> res) {
        if (left == n && right == n) {
            res.add(curStr);
            return;
        }

        // 剪枝
        if (left < right) {
            return;
        }

        if (left < n) {
            dfs(curStr + "(", left + 1, right, n, res);
        }
        if (right < n) {
            dfs(curStr + ")", left, right + 1, n, res);
        }
    }
}

回溯算法与深度优先遍历

回溯法采用试错的思想，它尝试分步去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其他的可能的分布解答再次尝试寻找问题的答案。回溯法通常用递归方法来实现，在反复重复上述的步骤之后可能出现两种情况：

找到一个可能存在的答案
在尝试了所有可能的分步方法后宣告该问题没有答案

深度优先搜索 算法（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点位置。如果还存咋未发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行指导所有节点都被访问为止。

「回溯算法」与「深度优先遍历」都有「不撞南墙不回头」的意思。「回溯算法」强调了「深度优先遍历」思想的用途，用一个 不断变化 的变量，在尝试各种可能的过程中，搜索需要的结果。强调了回退操作对于搜索的合理性。而「深度优先遍历」强调一种遍历的思想，与之对应的遍历思想是「广度优先遍历」。至于广度优先遍历为什么没有成为强大的搜索算法，我们在题解后面会提。

在「力扣」第 51 题的题解《回溯算法（第 46 题 + 剪枝）》中，展示了如何使用回溯算法搜索 4 皇后问题的一个解，相信对直观地理解「回溯算法」是有帮助。

搜索与遍历

我们每天使用的搜索引擎帮助我们在庞大的互联网上搜索信息。搜索引擎的「搜索」和「回溯搜索」算法里「搜索」的意思是一样的。

搜索问题的解，可以通过遍历实现。所以很多教程把「回溯算法」称为爆搜（暴力解法）。因此回溯算法用于搜索一个问题的所有的解，通过深度优先遍历的思想实现。

与动态规划的区别

共同点：用于求解多阶段决策问题。多阶段决策问题即：

求解一个问题分为很多步骤(阶段)
每个步骤(阶段) 可以有多种选择

不同点：

动态规划只需要求我们评估的最优解是多少，最优解对应的具体解是什么并不要求。因此很适合用于评估一个方案的效果。
回溯算法可以搜索得到所有的方案(当然也包括最优解)，但是本质上它是一种遍历算法，时间复杂度很高。

从全排列问题开始理解回溯算法

我们尝试在纸上写 3 个数字、4 个数字、5 个数字的全排列，相信不难找到这样的方法。以数组 [1, 2, 3] 的全排列为例。

先写以1开头的全排列，他们是: $[1,2,3],[1,3,2]$，即1 + $[2,3]$的全排列（注意：递归结构体现在这里）
再写以2开头的全排列，他们是: $[2,1,3],[2,3,1]$ ,即 2 + [1, 3] 的全排列；
最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

总结搜索的方法：按顺手枚举每一位可能出现的情况，已经选择的数字在当前要选择的数字中不能出现。按照这种策略就能做到不重不漏。这样的思路可以用一个树形结构表示。

说明：

每一个节点表示了求解全排列问题的不同阶段，这些阶段通过变量的「不同的值」体现，这些变量的不同的值，称之为「状态」；
使用深度优先遍历有「回头」的过程，在「回头」以后，状态变量需要设置成为和先前一样，因此在回到上一层结点的过程中，需要撤销上一次的选择，这个操作称之为「状态重置」；
深度优先遍历，借助系统栈空间，保存所需要的状态变量，在编码中只需要注意遍历到相应的节点的时候，状态变量的值是正确的，具体做法是：往下走一层的时候，path遍历在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此path变量是一个栈
深度优先遍历通过回溯操作，实现了全局使用一份状态变量的效果

使用编程的方法得到全排列，就是在这样的一个树形结构中完成遍历，从树的根结点到叶子结点形成的路径就是其中一个全排列。

设计状态变量

首先这棵树除了根节点和叶子结点以外，每一个结点做的事情其实是一样的，即：在已经选择了一些数的前提下，在剩下的还没有选择的数中，依次选择一个数，这样显然是一个递归的结构。
递归的终止条件是：一个排列的数字已经选够了，因此外卖需要一个变量来表示当前程序递归到第几层，外卖把这个变量叫做depath，或者index，表示当前要确定的是某个全排列中下标为index 的那个数是多少。
布尔数组 used，初始化的时候都为false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的对应位置设为 true，这样在考虑下一个位置的时候，就能以 $O(1)$ 的时间复杂度判断这个数是否被选择过，这是一种以空间换时间的思想。

这些变量称为「状态变量」，它们表示了在求解一个问题的时候所处的阶段。需要根据问题的场景设计合适的状态变量。

代码实现

46. 全排列

public class Solution{
  	public List<List<Integer>> permute(int[] nums){
      	int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0){
            return res;
        }
        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();
        dfs(nums, len, 0, path, used, res);
        return res;
    }
  	private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used,
                    List<List<Integer>> res){
      	if(depth == len){
          	res.add(path);
        }
      	// 在非叶子节点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然是通过一个循环实现。
      	for(int i=0;i<len;i++){
          	if(!used[i]){
              	path.add(nums[i]);
              	used[i]=true;
              	dfs(nums,len,depth+1,path,used,res);
              	//注意：下面这两行代码发生回溯，回溯发生从在深层节点回到浅层节点的过程，代码在形式上和递归前是对称的
              	used[i] = false;
              	path.remove(path.size() - 1);
            }
        }
    }
  
  	public static void main(String[] args){
      	int[] nums={1,2,3};
      	Solution solution = new Solution();
      	List<List<Integer>> lists = solution.permute(nums);
      	System.out.println(lists);
    }
}

class Solution:
    def permute(self, nums):
        size = len(nums)

        if len(nums) == 0:
            return []
        used = [False for _ in range(size)]
        res = []

        def dfs(nums, size, depth, path, used, res):
            if depth == size:
                res.append(path)
                return

            for i in range(size):
                if not used[i]:
                    used[i] = True
                    path.append(nums[i])
                    dfs(nums, size, depth + 1, path, used, res);
                    used[i] = False
                    path.pop()

        dfs(nums, size, 0, [], used, res)
        return res

if __name__ == '__main__':
    nums = [1, 2, 3]
    solution = Solution()
    res = solution.permute(nums)
    print(res)

执行 main 方法以后输出如下：

1	[[], [], [], [], [], []]

原因出现在递归终止条件这里：

if (depth == len) {
    res.add(path);
    return;
}

1
2
3

if depth == size:
		res.append(path)
    return

变量path 所指向的列表在深度优先遍历过程中只有一份，深度优先遍历完成以后，回到了根节点，成为空列表

在java中，参数传递是值传递，对象类型变量在传参的过程中，复制的是变量的地址。这些地址被添加到res变量，但实际上指向的是同一块内存地址，因此我们会看到6个空的列表对象。解决办法很简单，在 res.add(path)这里做一次拷贝即可。

if(depth == len){
  	res.add(new ArrayList<>(path));
  	return;
}

1
2
3

if depth == size:
  	res.append(path[:])
    return

复杂度分析：

回溯算法由于其遍历的特点，时间复杂度一般都比较高，有些问题分析起来很复杂。一些问题剪枝剪得好的话，复杂度会降的很低，因此分析最坏时间复杂度的意义不是很大。但视情况而定

时间复杂度 $O(N\times N!)$

非叶子结点的个数，一次为(按层数来)：

$1+A_N^1 + A_N^2 +...+A_N^{N-1} = 1 + \frac{N!}{(N-1)!} + \frac{N!}{(N-2)!} +...+N!$

1是根节点，在第一层，节点个数为 N个选一个的排列故为$A_N^1$

空间复杂度： $O(N\times N!)$

递归树深度 $logN$ ，全排列个数 $N!$ , 每个全排列占空间$N$ 。取较大者

为什么不是广度优先遍历

首先是正确性，只有遍历状态空间，才能得到所有符合条件的解，这一点 BFS 和 DFS 其实都可以；
在深度优先遍历的时候，不同状态之间的切换很容易，可以再看一下上面有很多箭头的那张图，每两个状态之间的差别只有 11 处，因此回退非常方便，这样全局才能使用一份状态变量完成搜索；
如果使用广度优先遍历，从浅层转到深层，状态的变化就很大，此时我们不得不在每一个状态都新建变量去保存它，从性能来说是不划算的；
如果使用广度优先遍历就得使用队列，然后编写结点类。队列中需要存储每一步的状态信息，需要存储的数据很大，真正能用到的很少。
使用深度优先遍历，直接使用了系统栈，系统栈帮助我们保存了每一个结点的状态信息。我们不用编写结点类，不必手动编写栈完成深度优先遍历。

做题的时候，建议先画树形图，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。

在画图的过程中思考清楚：