算法锦囊5：一文搞定回溯

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

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

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

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

概述

在上一篇文章中，我们重点学习了递归的解法，但其实在使用递归的过程中会发现，很多题也用了回溯的思想。其实，递归和回溯没有本质上的区别，都是把给定的问题拆解为子问题。

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。

回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

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

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

接下来，来看一些我精挑细选的题目。

78. 子集

该题来源于78. 子集。

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

我们先感性一下认识这道题，对于数组里每个元素，可以选，可以不选，有两种可能，n个元素就是2^n种选择。

每次选择或不选择元素之后，就继续往下递归，这个选或不选的动作，可以由回溯法来协调。

具体答案看下面的代码。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def _dfs(cur, index):
            # cur为当前结果，index为遍历的索引
            # 如果遍历索引走到最后了，则存储当前结果
            if index == len(nums):
                res.append(cur[:])
                return
            # 这一步代表使用当前索引的元素
            cur.append(nums[index])
            # 继续递归
            _dfs(cur, index+1)
            # 回溯，把当前元素给弹出
            cur.pop()
            # 继续递归
            _dfs(cur, index+1)

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

17. 电话号码的字母组合

接下来，趁热打铁，看这一题。17. 电话号码的字母组合。

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
复制代码

这一题同样也用到回溯，上一题的回溯体现在对于每个元素，选或者不选，而这一题对于每个元素，有多重可能性，比如2对应着“abc”，在确定元素2时，需要分别把“a”,“b”,“c”带进后面的递归里。

题解如下：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return list()
        
        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        def backtrack(index: int):
            if index == len(digits):
                res.append("".join(combination))
            else:
                digit = digits[index]
                for letter in phoneMap[digit]:
                    combination.append(letter)
                    backtrack(index + 1)
                    combination.pop()

        combination = list()
        res = list()
        backtrack(0)
        return res
复制代码

51. N皇后

接下来，我们来看回溯题里面超级经典一题，51. N 皇后。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
复制代码

这道题虽然是困难题，但是在我们弄懂回溯之后，就没那么复杂了。

思路在于，遍历每一行，不断去试错。这题比较麻烦的地方在于，如何判断是一组可行解。我的方法是用三个集合去存储已经遍历过的竖、撇、捺的坐标，如果在里面，则不是可行解。

这是我的代码：

class Solution:
    def __init__(self):
        self.res = 0

    def totalNQueens(self, n: int) -> int:
        col, pie, na = set(), set(), set()
        def _dfs(level):
            if level == n:
                self.res += 1
                return
            for j in range(0, n):
                if j in col or level + j in pie or level -j in na:
                    continue
                col.add(j)
                pie.add(level +j)
                na.add(level-j)
                _dfs(level + 1)
                col.remove(j)
                pie.remove(level +j)
                na.remove(level-j)

        _dfs(0)
        return self.res
复制代码

473. 火柴拼正方形

最后，我们用这道题来进行巩固。473. 火柴拼正方形

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]
输出: true
复制代码

这道题我曾经在面试里遇到过，一开始想用贪心，不过没解出来，后面才意识到需要用回溯。

正方形的周长是确定的，因此每条边的边长是确定的，以[1,1,2,2,2]为例，边长为2。

准备一个由四条边构成的数组，如[2,2,2,2]。依次用nums数组的元素去在该数组中扣除，等到nums元素遍历完了，去统计此时扣除完的结果是否是[0,0,0,0]。

我在算法里进行了一些优化。首先是利用了贪心的思路，先把数组由大到小排序，通常来讲，先去扣大的火柴棍更容易找到解。

另外就是在遍历火柴棍时，用到了剪枝。如果两个火柴棍长度一样，就没必要重复遍历了。

总之，这道题用到的知识点还是非常多的，边界判断+递归+回溯+贪心+剪枝，非常考验算法功底，强烈推荐做一下。

class Solution:
    def makesquare(self, nums: List[int]) -> bool:
        if not nums: return False
        s = sum(nums)
        # 如果周长不能被4整除，直接返回False
        if s % 4 != 0: return False
        w = s // 4
        # 先将数组从大到小排序，这里利用了贪心的思路，找到解的速度会快很多
        nums.sort(reverse=True)

        def _dfs(index, w_arr):
            # 数组用完了，边长数组必须都为0，否则返回False
            if index == len(nums):
                return all([i==0 for i in w_arr])
            result = False
            for j in range(len(w_arr)):
                # 这里用到了剪枝，如果w_arr连续两个值相同，则可以跳过
                if j > 0 and w_arr[j] == w_arr[j-1]:
                    continue
                # 依次尝试去扣除nums[index]
                if w_arr[j] >= nums[index]:
                    w_arr[j] -= nums[index]
                    if _dfs(index+1, w_arr):
                        return True
                    w_arr[j] += nums[index]
            return result

        return _dfs(0, [w,w,w,w])

复制代码