46. Permutations

  1. class Solution:
  2.     def permute(self, nums: List[int]) -> List[List[int]]:
  3.         def dfs(i):                 # 当前固定nums的第i位
  4.             if i == n-1:
  5.                 res.append(nums[:]) # copy而非传地址
  7.             for j in range(i, n):
  8.                 nums[i], nums[j] = nums[j], nums[i]
  9.                 dfs(i+1)
  10.                 nums[i], nums[j] = nums[j], nums[i]
  12.         n = len(nums)
  13.         res = []
  14.         dfs(0)
  15.         return res
  • 时间复杂度：回溯 backtrack - 图1，dfs()调用占回溯 backtrack - 图2，每次复制答案数组占回溯 backtrack - 图3
  • 空间复杂度：回溯 backtrack - 图4，取决于递归调用深度

47. Permutations II

给定数组含有重复元素，注意使用set来去重。

  1. class Solution:
  2.     def permuteUnique(self, nums: List[int]) -> List[List[int]]:
  3.         def dfs(i):
  4.             if i == n-1:
  5.                 res.append(nums[:])
  7.             num_set = set()        # 对每个位置，使用一个set来去重
  8.             for j in range(i, n):
  9.                 if nums[j] in num_set:
  10.                     continue
  11.                 num_set.add(nums[j])
  13.                 nums[i], nums[j] = nums[j], nums[i]
  14.                 dfs(i+1)
  15.                 nums[i], nums[j] = nums[j], nums[i]
  17.         n = len(nums)
  18.         res = []
  19.         dfs(0)
  20.         return res
  • 时间复杂度：回溯 backtrack - 图5
  • 空间复杂度：回溯 backtrack - 图6

39. Combination Sum

  1. class Solution:
  2.     def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
  4.         def dfs(i, path, remain):
  5.             if remain == 0:
  6.                 res.append(path)
  7.                 return
  9.             for j in range(i, len(nums)):
  10.                 if remain - nums[j] < 0:   # 剪枝
  11.                     break
  12.                 dfs(j, path + [nums[j]], remain - nums[j])
  14.         nums.sort()                        # 剪枝的预处理：排序
  15.         res = []
  16.         dfs(0, [], target)
  17.         return res

40. Combination Sum II

回溯 backtrack - 图7中可能包含重复元素，且每个元素只能使用一次：

  • 考虑剪枝：先排序，再判断剩余填充的值是否回溯 backtrack - 图8

  • 考虑重复元素：j > i and nums[j] == nums[j-1]

    class Solution:
  def combinationSum2(self, nums: List[int], target: int) -> List[List[int]]:
      '''
      i: 可以选择元素的起始坐标
      '''
      def dfs(i, path, remain):
          if remain == 0:
              res.append(path)
              return

          for j in range(i, len(nums)):
              if remain - nums[j] < 0:
                  break
              if j > i and nums[j] == nums[j-1]:  # 可选的重复元素：只能使用一次
                  continue
              dfs(j + 1, path + [nums[j]], remain - nums[j])

      nums.sort()
      res = []
      dfs(0, [], target)
      return res

77. Combinations

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:

        def dfs(i, path):
            if len(path) == k:
                res.append(path)
                return

            for j in range(i, n + 1):
                if j + (k - len(path)) >= n + 2:  # 剪枝
                    break
                dfs(j + 1, path + [j])

        res = []
        dfs(1, [])
        return res

78. Subsets

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(i, path):
            res.append(path)
            for j in range(i, n):
                dfs(j + 1, path + [nums[j]])

        n, res = len(nums), []
        dfs(0, [])
        return res

79. Word Search

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:

        # 搜索到board的(i, j)位置，word的k位置
        def dfs(i, j, k):
            if not 0 <= i < m or not 0 <= j < n or board[i][j] != word[k]:
                return False
            if k == len(word) - 1:   # 先进行char相等判断后，再进行index判断
                return True

            board[i][j] = '.'        # or 可采用visited = set()来记录(i, j)
            flag = dfs(i-1, j, k+1) or dfs(i+1, j, k+1) or \
                   dfs(i, j-1, k+1) or dfs(i, j+1, k+1)
                                     # 依序搜索，遇到True便剪枝（or具有短路特性）
            board[i][j] = word[k]    # 回溯

            return flag

        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False
  • 时间复杂度：回溯 backtrack - 图9，除了第一次可以进入回溯 backtrack - 图10个分支以外，其余时间我们最多会进入回溯 backtrack - 图11个分支（因为每个位置只能使用一次，所以走过来的分支没法走回去）
  • 空间复杂度：回溯 backtrack - 图12，递归调用的栈深度

51. N-Queens

**N-皇后**问题中，棋子🚩的摆放规则是：

  1. 不能在同一行/同一列；
  2. 不能在同一主/副对角线。

将N个皇后摆放在N × N的棋盘上，必然是每一行、每一列均有一个皇后，且没有两个皇后在同一对角线上。

考虑使用回溯法解决：
以**行**为基准放置皇后，判断该行的每一**列**是否能够放置皇后。显然每一行可放置的选择数依次是回溯 backtrack - 图13，故仅考虑遍历的时间复杂度为回溯 backtrack - 图14。
为了降低总的时间复杂度，考虑空间换时间：能否使用回溯 backtrack - 图15的时间判断该位置是否能否放置皇后？

Approach I** 基于`集合`的回溯**

  1. 列：回溯 backtrack - 图16 - 回溯 backtrack - 图17记录
  2. 主对角线：对于同一主对角线的元素，回溯 backtrack - 图18恒定

  3. 副对角线：对于同一主对角线的元素，回溯 backtrack - 图19恒定 ```python class Solution: def solveNQueens(self, n: int) -> List[List[str]]:

     def generate_board():
     board = []
     row = ['.'] * n
     for i in range(n):
         row[queens[i]] = 'Q'
         board.append(''.join(row))    # 每一行均是'str'而非'list'
         row[queens[i]] = '.'
     return board

    def dfs(i):                           # 在第i行放置棋子🚩
        if i == n:
            res.append(generate_board())
            return

        for j in range(n):
            if j in columns or i - j in diagonal_main or i + j in diagonal_sub:
                continue

            queens[i] = j
            columns.add(j)
            diagonal_main.add(i - j)
            diagonal_sub.add(i + j)

            dfs(i + 1)

            queens[i] = -1
            columns.remove(j)
            diagonal_main.remove(i - j)
            diagonal_sub.remove(i + j)


    queens = [-1] * n                     # queens[i] == j: [i, j]处放置有棋子🚩
    columns, diagonal_main, diagonal_sub = set(), set(), set()
    res = []
    dfs(0)
    return res


- 时间复杂度：![](https://cdn.nlark.com/yuque/__latex/3733142e935b34a156d2ca80dffda957.svg#card=math&code=O%28N%21%29&id=BjYRw)
- 空间复杂度：![](https://cdn.nlark.com/yuque/__latex/8c51f5913186f8ac629f1d5838940f33.svg#card=math&code=O%28N%29&id=rrfYb)，递归调用层数、数组长度、集合长度均为![](https://cdn.nlark.com/yuque/__latex/459f3c80a50b7be28751b0869ef5386a.svg#card=math&code=N&id=Ee3K9)

**Approach II**** 基于**`**bit**`**的回溯**<br />之后再学吧。

<a name="N8M6T"></a>
#### [93. Restore IP Addresses](https://leetcode-cn.com/problems/restore-ip-addresses/)
```python
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:

        SEG_COUNT = 4                  # ip地址固定分为4段
        segments = [''] * SEG_COUNT
        res = []

        # index: ip地址的段号
        # start: s中可选位置的起点
        def dfs(index, start):
            if index == SEG_COUNT:
                if start == len(s):
                    res.append('.'.join(segments))
                return

            if start == len(s):
                return

            if s[start] == '0':                 # 该bit为0，不能有前导0，直接加入
                segments[index] = '0'
                dfs(index + 1, start + 1)
                # return

            for end in range(start, len(s)):    # 有边界不能为start+3（比n大，越界）
                ip = s[start:end+1]
                if 0 < int(ip) <= 255:          # 不能使用str比较（字典序） and 不能包含0
                    segments[index] = ip
                    dfs(index + 1, end + 1)
                    # segments[index] = ''
                else:
                    break

        dfs(0, 0)
        return res
  • 时间复杂度：回溯 backtrack - 图20，递归最大深度为回溯 backtrack - 图21，每次最多有三种选择（1bit, 2bits, 3bits），每次复制到答案数组的时间开销为回溯 backtrack - 图22
  • 空间复杂度：回溯 backtrack - 图23，递归最大深度为回溯 backtrack - 图24