回溯

约 700 个字 94 行代码 1 张图片预计阅读时间 4 分钟总阅读量次

39. 组合总数

🔑🔑 难度：Medium 中等

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        n = len(candidates)
        def dfs(curr, curr_list, idx):
            if curr > target:
                return 

            if curr == target:
                res.append(curr_list)
                return 

            for i in range(idx, n):
                dfs(curr + candidates[i], curr_list + [candidates[i]], i )

        dfs(0, [], 0)
        return res

思路就是每次放一个数字，但是要保证递归下去的时候总是从当前数字向后开始递归。

51. N 皇后

🔑🔑 难度：High 困难

示例1:

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:

        def generateBoard():
            board = []
            for i in range(n):
                rows[queens[i]] = 'Q'
                board.append("".join(rows))
                rows[queens[i]] = '.'
            return board

        def backtrack(idx):
            if idx == n:
                board = generateBoard()
                solutions.append(board)
            else:
                for i in range(n):
                    if i in columns or idx - i in diagnose1 or idx + i in diagnose2:
                        continue
                    columns.add(i)
                    diagnose1.add(idx - i)
                    diagnose2.add(idx + i)
                    queens[idx] = i
                    backtrack(idx + 1)
                    columns.remove(i)
                    diagnose1.remove(idx - i)
                    diagnose2.remove(idx + i)


        rows = ["."] * n
        queens = [-1] * n
        columns = set()
        diagnose1 = set()
        diagnose2 = set()
        solutions = []
        backtrack(0)
        return solutions

最经典的回溯题。

第一，如何表示整个棋盘？一个列表足以。row = [2,0,1,3] ，第 i 个元素表示第 i 行的皇后在第 row[i] 列。

第二，这个回溯每次backtrack之后都是需要恢复原始状态的，表明忽略刚刚的操作。

第三，terminal 条件：一旦所有的行都被安排了Queen，直接返回；

第四，也是最重要的，如何判断冲突？一个set来记录已经安排的列，一个set来记录已经安排的左对角线，一个set来记录已经安排的右对角线。idx - i 就是被占用的对角线。

如此，以上。

131. 分割回文字符串

DP，记录“从i到j的字串是否回文”，然后再回溯。

🔑🔑 难度：Medium 中等

示例1: 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"

输出：[["a","a","b"],["aa","b"]]

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        dp = [[True for _ in range(n)] for _ in range(n)]

        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

        res = []
        temp = []
        def dfs(idx):
            if idx == n:
                res.append(temp[:])
                return 
            for i in range(idx, n):
                if dp[idx][i]:
                    temp.append(s[idx: i + 1])
                    dfs(i + 1)
                    temp.pop()

        dfs(0)
        return res

重要的是dp的过程啊!!因为要返回所有的回文串.. DP的第一个for循环要从后到前面开始。因为从 i 到 j 的字串是回文，意味着 s[i] == s[j] 以及 s[i + 1: j - 1]的串是回文的

46.全排列

🔑🔑 难度：Medium 中等

示例1: 输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

hehh

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        def backtrack(cur, rest):

            if len(cur) == len(nums):
                result.append(cur)
                return
            for i in range(len(rest)):
                tmp = copy.copy(cur)
                cur.append(rest[i])
                backtrack(cur, rest[:i] + rest[i + 1:])
                cur = tmp

        backtrack([], nums)
        return result