粗暴力搜索，回溯算法不是求最优解，而是求所有可行解。

1. 组合问题（不看元素顺序）
2. 切割问题
3. 子集问题
4. 排列问题（强调元素顺序）
5. 棋盘问题
6. 行程问题

一、回溯

回顾下多叉树的遍历框架：

def dfs(root):
  if not root: return 
  for child in root.children：
    dfs(child )

而回溯算法的模板和多叉树遍历的模板非常相似：

result= []
def backtracking(路径, 选择列表):
  if(满足终止条件):
    result.append(路径)  # 收集结果
    return
    
  for 选择 in 选择列表:
    做选择
    backtracking(路径, 选择列表)
    回溯操作/撤销操作

1、组合问题

思路：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选取第三个…。

leetcode77. 组合

77. 组合

回溯暴力解决方法：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(start, path, res, n, k):
            if len(path) == k:
                res.append(path[:])
                return 

            # 添加start
            # 1、防止出现同一个原始重复使用的现象如：11 22 33 44
            # 2、防止出现 12 21这种重复出现的现象
            # [[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]]
            # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
            for i in range(start, n+1):
                path.append(i)
                backtracking(i+1, path, res, n, k)
                path.pop()
        path, res = [], []
        backtracking(1, path, res, n, k)
        return res

剪枝版本（速度大大增加）：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(start, path, res, n, k):
            if len(path) == k:
                res.append(path[:])
                return 

            # 添加start
            # 1、防止出现同一个原始重复使用的现象如：11 22 33 44
            # 2、防止出现 12 21这种重复出现的现象
            # [[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]]
            # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
            # 剪枝：搜索起点的上界 = n + 1 - 还需要选择的元素个数
            for i in range(start, n+1-(k-len(path))+1):
                path.append(i)
                backtracking(i+1, path, res, n, k)
                path.pop()
        path, res = [], []
        backtracking(1, path, res, n, k)
        return res

解析：原先的回溯暴力解法效率不是很高，因为是在遍历所有的可能，做了很多的无用功。比如：n=7, k=4时，从5开始搜索已经没有意义了，即使5选上，加上6和7，也凑不到4个数。所以可以知道，搜索起点是有上界的，而不是上面的 [i:n+1]

再多举几个例子（n=6，k=4）：

• 当len(path)==0:还需要选4个数，搜索起点最大（搜索起点的上界限）是3
• 当len(path)==1: 还需要选3个数，搜索起点最大（搜索起点的上界限）是4
• 当len(path)==2:还需要选2个数，搜索起点最大（搜索起点的上界限）是5
• 当len(path)==3:还需要选1个数，搜素起到最大（搜索起点的上界限）是6

可以发现规律：

搜索起点的上界 + 还需要选择的元素个数 - 1 = n
搜索起点的上界 = n + 1 - 还需要选择的元素个数

leetcode39. 组合总和

39. 组合总和

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtracking(start, path, res, candidates, target):
            if target == 0:
                res.append(path[:])
                return
            # 结果 [[2,2,3],[7]]
            for i in range(start, len(candidates)):
                # 剪枝 小于0以后就不用再加进去了 之后的数肯定也是小于1的
                if candidates[i] <= target:
                    path.append(candidates[i])
                    # i: 防止出现 223 232 322重复出现
                    # i+1: 会把223给舍去
                    backtracking(i, path, res, candidates, target-candidates[i])
                    path.pop()
        path, res = [], []
        candidates.sort()
        backtracking(0, path, res, candidates, target)
        return res

leetcode40. 组合总和 II（经典）

40. 组合总和 II

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 条件：包含重复数字数组  数组中每个数字在每个组合中只能用一次  解集不能重复
        def backtracking(start, path, res, candidates, target):
            if target == 0:
                res.append(path[:])
                return  # 不需要再加进path
            for i in range(start, len(candidates)):
                # 剪枝 小于0以后就不用再加进去了 之后的数肯定也是小于1的
                if candidates[i] <= target:
                    # # 同一层 出现相同的元素 直接跳过
                    if i>start and candidates[i] == candidates[i-1]:
                        continue
                    path.append(candidates[i])
                    backtracking(i+1, path, res, candidates, target-candidates[i])
                    path.pop()
        res, path = [], []
        candidates.sort()  # 一定要排序
        backtracking(0, path, res, candidates, target)
        return res

leetcode216. 组合总和 III

216. 组合总和 III

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def backtracking(start, path, res, k, n):
            if n == 0 and len(path) == k:
                res.append(path[:])
                return 
            for i in range(start, 10):
                if n > 0:
                    path.append(i)
                    backtracking(i+1, path, res, k, n-i)
                    path.pop()
        path, res = [], []
        backtracking(1, path, res, k, n)
        return res

leetcode17. 电话号码的字母组合

17. 电话号码的字母组合

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "": return []
        keyboard = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno',
                    '7':'pqrs', '8':'tuv', '9':'wxyz'}
        def backtracking(start, path, res, digits, keyboard):
            if len(path) == len(digits):
                res.append(''.join(path[:]))
                return
            curList = keyboard[digits[start]]
            for c in curList:
                path.append(c)
                backtracking(start+1, path, res, digits, keyboard)
                path.pop()
        path, res = [], []
        backtracking(0, path, res, digits, keyboard)
        return res

2. 切割问题

思路：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…。

leetcode131. 分割回文串

131. 分割回文串

视频

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def isPal(c):
            for i in range(len(c) // 2):
                if c[i] != c[~i]: return False
            return True
        def backtracking(start, path, res, s):
            if start == len(s):
                res.append(path[:])
                return
            for i in range(start, len(s)):
                # if s[start:i+1] == s[start:i+1][::-1]:
                # 判断之前截取的一段[start:i+1]是否是回文子串 
                if isPal(s[start:i+1]):
                    path.append(s[start:i+1])
                    # 上一段截取的是回文子串 开始继续截取下一段 从i+1开始
                    backtracking(i+1, path, res, s)
                    path.pop()
        res, path = [], []
        backtracking(0, path, res, s)
        return res 

leetcode93. 复原 IP 地址

93. 复原 IP 地址

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        if len(s) > 12 or len(s) < 4 or len(s) == 0: return []
        def isMeeting(patch):
            # 长度不能小于1或者大于3
            if len(patch) < 1 or len(patch) > 3: return False
            # 长度大于1时不能以0开头
            if len(patch) > 1 and patch[0] == '0': return False
            # 长度等于3时不能大于255
            if len(patch) == 3:
                count = int(patch[0])*100 + int(patch[1])*10 + int(patch[2])
                if count > 255: return False
            return True
        def backtracking(start, path, res, s, depth):
            if depth == 3:
                if isMeeting(s[start:]):
                    res.append('.'.join(path + [s[start:]]))
                    return 
            for i in range(start, len(s)):
                if isMeeting(s[start:i+1]):
                    path.append(s[start:i+1])
                    backtracking(i+1, path, res, s, depth+1)
                    path.pop()
        res, path = [], []
        backtracking(0, path, res, s, 0)
        return res

3、子集问题

leetcode78. 子集

78. 子集

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtracking(start, path, res, nums):
            # 注意这里的递归出口的条件
            if start > len(nums): return 
            res.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtracking(i+1, path, res, nums)
                path.pop()
        res, path = [], []
        backtracking(0, path, res, nums)
        return res

leetcode90. 子集 II

90. 子集 II

视频 这道题和之前的组合总和第二题思路完全一样。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def backtracking(start, path, res, nums):
            if start > len(nums): return
            res.append(path[:])
            for i in range(start, len(nums)):
                # 在同一层里 如果[1]选过了2->[1,2] 那么下一次[1]再碰到2就直接跳过
                if i > start and nums[i] == nums[i-1]:
                    continue
                path.append(nums[i])
                backtracking(i+1, path, res, nums)
                path.pop()
        path, res = [], []
        nums.sort()
        backtracking(0, path, res, nums)
        return res

leetcode491. 递增子序列

491. 递增子序列

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        # 1、长度至少为2 
        # 2、必须递增(可以相等)
        # 3、不重复
        def backtracking(start, path, res, nums):
            # 长度至少为2
            if len(path) >= 2: 
                res.append(path[:])
                # 注意这里没有return 因为当前path找到一个还需要继续往下找
            # 在不能sort的情况下排除当前层的重复结果一般是使用一个used数组
            used = []
            for i in range(start, len(nums)):
                # 保证递增  保证不重复(判断当前层有没有用过nums[i])
                if (len(path)>0 and path[-1] > nums[i]) or nums[i] in used:
                    continue
                path.append(nums[i])
                used.append(nums[i])
                backtracking(i+1, path, res, nums)
                path.pop()
        res, path = [], []
        backtracking(0, path, res, nums)
        return res

4、排列问题

leetcode46. 全排列

46. 全排列

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 数字不重复的数组 全排列 答案不能相同  
        def backtracking(path, res, nums, used):
            if len(path) == len(nums): 
                res.append(path[:])
                return 
            for i in range(len(nums)):
                if used[i] == 1: continue  # 每个元素只能用一次
                path.append(nums[i])
                used[i] = 1
                backtracking(path, res, nums, used)
                used[i] = 0
                path.pop()
        path, res = [], []
        used = [0] * len(nums)
        backtracking(path, res, nums, used)
        return res

leetcode47. 全排列 II（经典）

47. 全排列 II

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 可重复数组 全排列 不重复
        def backtracking(path, res, nums, used):
            if len(path) == len(nums): 
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i] == 1: continue
                # 减去重复的结果 
                # i>0 进入该层>=2个数 如果当前层和前面层相同 且前面层访问过了 剪掉 ？？？
                if i>0 and nums[i]==nums[i-1] and not used[i-1]: continue
                path.append(nums[i])
                used[i] = 1
                backtracking(path, res, nums, used) # 进入下一层
                used[i] = 0
                path.pop()
        path, res = [], []
        used = [0] * len(nums)
        nums.sort()
        backtracking(path, res, nums, used)
        return res

5、棋盘问题

leetcode51. N 皇后

51. N 皇后

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 同一行 board[1][0] [1][1] [1][2] [1][3] [1][4]
        # 同一列 board[0][1] [1][1] [2][1] [3][1] [4][1]
        # 斜行   board[1][0] [2][1] [3][2] [4][3] 差值相同
        #        board[1][3] [2][2] [3][1] 和值相同
        # 这种方法时间复杂度较高
        def check(board, row, col):
            for i in range(n):
                if board[row][i] == 'Q' or board[i][col] == 'Q': return False
            for i in range(n):
                for j in range(n):
                    if ((i+j) == (row+col) and board[i][j] == 'Q') or ((i-j) == (row-col) and board[i][j] == 'Q'): return False
            return True
        def backtracking(res, board, row):
            if row == n:
                res.append([''.join(row) for row in board])
                return
            for i in range(n):
                if check(board, row, i) == True:
                    board[row][i] = 'Q'
                    backtracking(res, board, row+1)
                    board[row][i] = '.'
        board = [['.']*n for i in range(n)]
        res = []
        backtracking(res, board, 0)
        return res

leetcode37. 解数独

37. 解数独

难度高，第二轮复习再更新

6、行程问题

leetcode332. 重新安排行程

332. 重新安排行程

难度高，第二轮复习再更新
学习

最后

以上就是含糊橘子为你收集整理的【Leetcode 专题二（回溯专题）】组合、切割、子集、排序、棋盘、行程问题一、回溯4、排列问题5、棋盘问题6、行程问题的全部内容，希望文章能够帮你解决【Leetcode 专题二（回溯专题）】组合、切割、子集、排序、棋盘、行程问题一、回溯4、排列问题5、棋盘问题6、行程问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。