算法锦囊4：一文搞定递归

这是我参与更文挑战的第10天，活动详情查看： 更文挑战

最近想把自己刷算法题的经验心得整理一下，一方面为了复习巩固，另一方面也希望我的分享能够帮助到更多在学习算法的朋友。

专栏名称叫《算法锦囊》，在讲解算法时会注重整体性，但不会面面俱到，适合有一定算法经验的人阅读。

这一次我们重点来看递归，这一部分的所有题目和源码都上传到了github的该目录下，题解主要用Python语言实现。

概述

递归题目都会将给定的问题拆解为子问题，直到到子问题成为一个不可以拆分的、可以直接求解的最简单问题。

递归，回溯，分治某种程度上而言，他们的本质上没有太多区别，只是在细节上的处理不一样。

递归可以用以下代码模板：

• 1. 判断终止条件
• 2. 处理当前逻辑
• 3. 不断下探
• 4. 清理当前层（非必须）

def recursion(level, param1, param2, ...): 
    # recursion terminator 
    if level > MAX_LEVEL: 
       process_result 
       return 
    # process logic in current level 
    process(level, data...) 
    # drill down 
    self.recursion(level + 1, p1, ...) 
    # reverse the current level status if needed
复制代码

接下来我们看几道经典的例题。

22. 括号生成

该题来源于22. 括号生成。

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
复制代码

这是一道非常经典的递归题，直接上代码，我在题解内注释了前面代码模板里的位置。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def _dfs(left, right, path):
            # 1. 判断终止条件
            if left == right == 0:
                res.append(path)
                return
            # 2. 处理当前逻辑
            # 3. 不断下探
            if left > 0:
                _dfs(left-1, right, path + '(')
            if right > left:
                _dfs(left, right-1, path + ')')
        res = []
        _dfs(n, n, '')
        return res
复制代码

这道题的解法非常多，我另外提供回溯法以及广度优先搜索的思路，以帮助开阔大家眼界。

回溯法，回溯法的特点体现在处理当前逻辑时存在试错的步骤。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def traceback(left, right, cur):
            if left == right == n:
                res.append(''.join(cur))
                return
            if left < n:
                cur.append('(')
                traceback(left+1, right, cur)
                cur.pop()
            if right < left and right < n:
                cur.append(')')
                traceback(left, right+1, cur)
                cur.pop()

        res = []
        traceback(0, 0, [])
        return res
复制代码

广度优先搜索，即BFS的方法。它的特点是使用一个队列，类似树的层序遍历。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res, queue = [], []
        queue.append(('',n,n))
        while queue:
            path, left, right = queue.pop(0)
            if left == right == 0:
                res.append(path)
                continue
            if left > 0: queue.append((path+'(', left-1, right))
            if right > left: queue.append((path+')', left, right-1))
        return res
复制代码

77. 组合

该题来源于77. 组合。

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
复制代码

注意这道题目很容易做的很复杂，在递归里面，建议传入数组的索引就可以了，无需传整个数组。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def _dfs(cur, index):
            if len(cur) == k:
                res.append(cur)
                return
            for i in range(index, n+1):
                _dfs(cur+[i], i+1)
        res = []
        _dfs([], 1)
        return res
复制代码

46. 全排列

该题来源于46. 全排列。

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
复制代码

先提供递归的解法，跟组合的区别是，取值的范围不一样。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def _dfs(cur, rest):
            if not rest:
                res.append(cur)
            for i in range(len(rest)):
                _dfs(cur+[rest[i]], rest[0:i] + rest[i+1:])

        _dfs([], nums)
        return res
复制代码

另一种方法就是用回溯，使用一个数组来进行标记该元素有没有被使用过。标记法在回溯中也是非常常用的方法。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def _dfs(cur):
            if len(cur) == len(nums):
                res.append(cur)
            for i in range(len(nums)):
                if used[i]:
                    continue
                used[i] = 1
                _dfs(cur+[nums[i]])
                used[i] = 0
        res = []
        used = [0]*len(nums)
        _dfs([])
        return res
复制代码

同样，这道题也可以用BFS。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        queue = [[]]
        level = 0
        while queue:
            # popleft node
            l = len(queue)

            for _ in range(l):
                cur = queue.pop(0)
                for j in range(len(nums)):
                    if nums[j] not in cur:
                        new = cur + [nums[j]]
                        queue.append(new)
            level += 1
            if level == len(nums):
                return queue
        return []
复制代码

最后，我们通过一道题目来复习一下递归。

全排列这道题的升级版为47. 全排列 II。

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
复制代码

在46题的基础上，对选取数组那里，多了一些细节处理，整体代码风格和全排列类似。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def _dfs(cur):
            if len(cur) == len(nums):
                res.append(cur)
            for i in range(len(nums)):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i-1] and used[i-1] == 0:
                    continue
                used[i] = 1
                _dfs(cur+[nums[i]])
                used[i] = 0
        nums.sort()
        res = []
        used = [0]*len(nums)
        _dfs([])
        return res
复制代码