LeetCode算法题整理（回溯篇）BackTracking

93. Restore IP Addresses

恢复IP地址。原题

1 2	Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"]

方法一：需要注意0的情况。

def restoreIpAddresses(self, s: str) -> List[str]:
    
    def backtrack(i, p):
        if i == N and len(p)==4:
            ans.append('.'.join(p))
            return
        if len(p) > 4: return
        for j in range(1, 4):
            cur = s[i:i+j]
            if cur and (not cur.startswith('0') or cur=='0') and int(cur) < 256:
                p.append(s[i:i+j])
                backtrack(i+j, p)
                p.pop()

    ans, N = [], len(s)
    backtrack(0, [])
    return ans

131. Palindrome Partitioning

回文串切分。原题

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

方法一：原始回溯。

def partition(self, s: str) -> List[List[str]]:

    def backtrack(s, remain):
        if not remain:
            ans.append(s)
        else:
            for i in range(1, len(remain)+1):      # 这里是n+1，因为整个字符串也有可能。
                if remain[:i] == remain[:i][::-1]:
                    backtrack(s+[remain[:i]], remain[i:])
    ans = []
    if s:
        backtrack([], s)
    return ans

方法二：使用列表生成式。

def partition(self, s: str) -> List[List[str]]:
    return s and [[s[:i]] + suffix 
                  for i in range(1, len(s)+1) if s[:i]==s[i-1::-1]
                  for suffix in self.partition(s[i:])] or [[]]

77. Combinations

实现组合。原题

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

方法一：回溯。700ms, 比Solution中的慢了100ms.

def combine(self, n: int, k: int) -> List[List[int]]:
    
    def backtrack(a, k, rest):
        if k == 1:
            ans.extend(a+[num] for num in rest)
        else:
            for i, h in enumerate(rest):
                backtrack(a+[h], k-1, rest[i+1:])
        
    ans = []
    backtrack([], k, list(range(1, n+1)))
    return ans

方法二：Solution中的递归。

def combine(self, n: int, k: int) -> List[List[int]]:
    
    def backtrack(first=1, cur=[]):
        if len(cur) == k:
            ans.append(cur[:])
        else:
            for i in range(first, n+1):
                cur.append(i)
                backtrack(i+1, cur)
                cur.pop()
        
    ans = []
    backtrack()
    return ans

方法三：列表生成式写法，递归。

def combine(self, n: int, k: int) -> List[List[int]]:
    if k == 0:
        return [[]]
    return [pre+[i] for i in range(k, n+1)
            for pre in self.combine(i-1, k-1)]

39. Combination Sum

和77类似，找出和为指定数值的组合，候选数字可以重复使用。原题

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

方法一：将候选组排序，并记录当前的索引值。

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    
    def backtrack(g, i, target):
        if target == 0:
            ans.append(g)
        elif target < candidates[i]:
            return
        for j in range(i, n):
            backtrack(g+[candidates[j]], j, target-candidates[j])
    
    ans = []
    n = len(candidates)
    candidates.sort()
    backtrack([], 0, target)
    return ans

方法二：时隔一年又重做一遍，感觉方法更加精炼了。sort感觉没啥必要。

def combinationSum(self, cn: List[int], target: int) -> List[List[int]]:

    def backtrack(i, t, p):
        if t == 0:
            ans.append(p[:])
            return
        if t < 0:
            return
        for j in range(i, len(cn)):
            c = cn[j]
            p.append(c)
            backtrack(j, t-c, p)
            p.pop()

    ans = []
    backtrack(0, target, [])
    return ans

40. Combination Sum II

组合求和，和39类似，区别在于候选数字中可能有重复数字，但每个数字只能使用一次。原题

麻烦的地方在于如何保证结果是非重复的。当j==i时，cn[j]==cn[j-1]说明前面刚刚用了和这个一样的数字。可以继续使用。比如[1,1,6]。当j!=i，cn[j]==cn[j-1]时，说明想以j开头同样找数组，这样肯定会找出一个重复的。

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    
    def backtrack(g, i, target):
        if target == 0:
            ans.append(g)
            return 
        for j in range(i, n):
            # avoid duplicate result
            if j != i and candidates[j]==candidates[j-1]:
                continue
            if candidates[j] > target:
                break
            backtrack(g+[candidates[j]], j+1, target-candidates[j])
    
    ans = []
    n = len(candidates)
    candidates.sort()
    backtrack([], 0, target)
    return ans

216. Combination Sum III

组合求和，从1~9选出k个不重复的数，和为n。原题

1 2	Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]

def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    def backtrack(g, i, target, k):
        if k==0 and target==0:
            ans.append(g)
        if k < 0 or target < 0:
            return
        for j in range(i, 10):
            backtrack(g+[j], j+1, target-j, k-1)
    
    ans = []
    backtrack([], 1, n, k)
    return ans

方法二：递归，使用last作为上限。

def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    
    def combs(k, n, cap):
        if not k:
            return [[]] * (not n)
        return [comb + [last]
                for last in range(1, cap)
                for comb in combs(k-1, n-last, last)]
    return combs(k, n, 10)

78. Subsets

输出给定无重复集合的子集组合。原题

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

方法一：常规写法。

def subsets(self, nums: List[int]) -> List[List[int]]:
    
    def backtrack(g, i, n):
        if not n:
            ans.append(g)
        for j in range(i, len(nums)):
            backtrack(g+[nums[j]], j+1, n-1)
    
    ans = []
    for n in range(len(nums)+1):
        backtrack([], 0, n)
    return ans

方法二：做一个递增就好了。

def subsets(self, nums: List[int]) -> List[List[int]]:
    ans = [[]]
    for num in nums:
        ans += [pre+[num] for pre in ans]
    return ans

方法三：使用索引来做。

def subsets(self, nums: List[int]) -> List[List[int]]:
    self.ans = []

    def dfs(i, n, p):
        if not n:
            self.ans.append(p[:])
            return
        for j in range(i, len(nums)):
            d = nums[j]
            p.append(d)
            dfs(j+1, n-1, p)
            p.pop()

    [dfs(0, i, []) for i in range(0, len(nums)+1)]
    return self.ans

90. Subsets II

和78类似，区别在于给定的数组有重复元素。原题

方法一：用到了40题中解法去重的代码。

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    
    def backtrack(g, i, n):
        if not n:
            ans.append(g)
        for j in range(i, len(nums)):
            if j!=i and nums[j]==nums[j-1]:
                continue
            backtrack(g+[nums[j]], j+1, n-1)
    
    ans = []
    nums.sort()
    for n in range(len(nums)+1):
        backtrack([], 0, n)
    return ans

79. Word Search

矩阵中的路径。原题

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

def exist(self, g: List[List[str]], word: str) -> bool:

    def dfs(i, j, word):
        if not word:
            return True
        original, g[i][j] = g[i][j], '-'
        for x, y in ((i+1, j), (i, j+1), (i, j-1), (i-1, j)):
            if 0<=x<R and 0<=y<C and g[x][y] == word[0]: 
                if dfs(x, y, word[1:]):
                    return True
        g[i][j] = original
        return False

    R, C = len(g), len(g[0])
    for i in range(R):
        for j in range(C):
            if g[i][j] == word[0] and dfs(i, j, word[1:]):
                return True
    return False

200. Number of Islands

小岛的个数。原题

Input:
11110
11010
11000
00000

Output: 1

方法一：常规写法。

def numIslands(self, grid: List[List[str]]) -> int:
    if not grid:
        return 0
    R, C = len(grid), len(grid[0])
    seen = set()
    count = 0
    
    def spread(i, j):
        seen.add((i, j))
        for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
            if (0<=x<R and 0<=y<C and (x, y) not in seen
                    and grid[x][y]=='1'):
                spread(x, y)
    
    for i in range(R):
        for j in range(C):
            if (i, j) not in seen and grid[i][j]=='1':
                count += 1
                spread(i, j)
    return count

方法二：当登录一座岛屿时，使这座岛屿下沉，变为’0’。不明白为什么比上个方法慢了20ms。

def numIslands(self, grid: List[List[str]]) -> int:
    
    def sink(i, j):
        if 0<=i<len(grid) and 0<=j<len(grid[i]) and grid[i][j]=='1':
            grid[i][j] = '0'
            list(map(sink, (i-1, i+1, i, i), (j, j, j-1, j+1)))   # important, return generator without list
            return 1
        return 0
    return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))

1254. Number of Closed Islands

和200类似，但是与边界相连的岛不能算了。原题

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

方法一：下沉法。先把边界的岛屿处理，然后再累计。

def closedIsland(self, g: List[List[int]]) -> int:
    m, n = len(g), len(g[0])
    
    def sink(i, j):
        if m>i>=0<=j<n and g[i][j]==0:
            g[i][j] = 1
            list(map(sink, (i-1, i+1, i, i), (j, j, j-1, j+1)))
            return 1
        return 0

    list(map(sink, [0]*n, range(n)))
    list(map(sink, [m-1]*n, range(n)))
    list(map(sink, range(m), [0]*m))
    list(map(sink, range(m), [n-1]*m))
    return sum(sink(i, j) for i in range(1, m-1) for j in range(1, n-1))

130. Surrounded Regions

将四周被包围的`O`翻转成`X`，边缘不算包围。原题

方法一：传统的方法在延伸的时候判断不出是否到达边界。所以这里先得到边界的点，然后从边界往里延伸，将所有的O变为S，第二次遍历时，将S恢复成O，其他设为X。

def solve(self, board: List[List[str]]) -> None:
    if not board: return
    R, C = len(board), len(board[0])
    bounds = [(i, j) for k in range(R+C) 
              for i, j in ((0, k), (R-1, k), (k, 0), (k, C-1))
              if i < R and j < C]
    while bounds:
        x, y = bounds.pop()
        if 0<=x<R and 0<=y<C and board[x][y]=='O':
            board[x][y] = 'S'
            bounds += (x-1, y), (x+1, y), (x, y-1), (x, y+1)
    board[:] = [['XO'[c=='S'] for c in row] for row in board]

417. Pacific Atlantic Water Flow

太平洋大西洋水流向，假设陆地上可以沿着高度不高于的地方流淌，求能同时流入两个海洋的陆地坐标。原题

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
 
 Pacific  ~   ~   ~   
       ~  1   2  (3)  *
       ~ (8) (9) (4)  *
       ~ (7) (6) (5)  *
          *   *   *   * Atlantic

方法一：一开始我以为从左上的点只能往右或下方向找陆地，事实上还是要寻找四个方向。这应该是最暴力的解法了。但是看了几个高票答案都没我这个快。

def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
    if not matrix:
        return []
    p_land = set()
    a_land = set()
    R, C = len(matrix), len(matrix[0])
    def spread(i, j, land):
        land.add((i, j))
        for x, y in ((i+1, j), (i, j+1), (i-1, j), (i, j-1)):
            if (0<=x<R and 0<=y<C and matrix[x][y] >= matrix[i][j]
                    and (x, y) not in land):
                spread(x, y, land)
                
    for i in range(R):
        spread(i, 0, p_land)
        spread(i, C-1, a_land)
    for j in range(C):
        spread(0, j, p_land)
        spread(R-1, j, a_land)
    return list(p_land & a_land)

526. Beautiful Arrangement

完美安排，给定1~N的数字，生成一种排列，是第i位的数字能被i整除，或者i能被第i位的数字整除，索引从1开始。原题

Input: 2
Output: 2
Explanation: 

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

方法一：常规写法，1300ms，beats50%.

def countArrangement(self, N: int) -> int:

    def backtrack(g, rest):
        nonlocal count
        if not rest:
            count += 1
        index = len(g) + 1
        for i, num in enumerate(rest):
            if num % index == 0 or index % num == 0:
                # print(g, i, num, index, rest)
                g.append(num)
                backtrack(g, rest[:i]+rest[i+1:])
                g.pop()
    count = 0
    backtrack([], list(range(1, N+1)))
    return count

方法二：去掉了方法一中一些无用的空间和操作。1000ms, beats 67%.

def countArrangement(self, N: int) -> int:
        
    def backtrack(g):
        nonlocal count
        if not rest:
            count += 1
        index = len(g) + 1
        for num in rest:
            if num % index == 0 or index % num == 0:
                g.append(num)
                rest.remove(num)
                backtrack(g)
                g.pop()
                rest.add(num)
    count = 0
    rest = set(range(1, N+1))
    backtrack([])
    return count

方法三：这里从后往前构建，最后构造1，因为1的位置放任何数字都可以。152ms

def countArrangement(self, N: int) -> int:
        
    def backtrack(i, rest):
        if i == 1:
            return 1
        return sum(backtrack(i-1, rest-{x})
                   for x in rest
                   if x % i == 0 or i % x == 0)
    return backtrack(N, set(range(1, N+1)))

方法四：在3的基础上优化，每次调用方法时可以利用之前的结果。52ms

cache = {}
class Solution:
    def countArrangement(self, N: int) -> int:
            
        def backtrack(i, rest):
            if i == 1:
                return 1
            key = i, rest
            if key in cache:
                return cache[key]
            ans =  sum(backtrack(i-1, rest[:j]+rest[j+1:])
                       for j, x in enumerate(rest)
                       if x % i == 0 or i % x == 0)
            # print(ans, i, rest)
            cache[key] = ans
            return ans
        return backtrack(N, tuple(range(1, N+1)))

22. Generate Parentheses

生成n对合法的括号。原题

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

方法一：常规写法。

def generateParenthesis(self, n: int) -> List[str]:
    
    def backtrack(p, l, r):
        if len(p) == n*2:
            ans.append(p)
        if l < n:
            backtrack(p+'(', l+1, r) 
        if r < l:
            backtrack(p+')', l, r+1)
    ans = []
    backtrack('', 0, 0)
    return ans

方法二：生成器写法。

def generateParenthesis(self, n: int) -> List[str]:
    
    def gen_parens(p, l, r):
        if r >= l >= 0:
            if not r:
                yield p
            yield from gen_parens(p+'(', l-1, r)
            yield from gen_parens(p+')', l, r-1)
    return list(gen_parens('', n, n))

89. Gray Code

灰码问题。给定一个n表示n位。从0开始每次改变一个位的数字，产生所有的组合。原题

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1

方法一：回溯法。一定要有顺序，一开始我误以为n位的进制0或1的组合。但是不行，因为不能从01跨越到10。这个问题我想了很久没有想出来如何解决，看到discuss中一个java版本的受到了启发。

def grayCode(self, n: int) -> List[int]:
    
    def backtrack(p, n):
        if not n:
            ans.append(int(''.join(p), 2))
            return
        for i in range(2):
            p += binary[i]
            if p[-1] == '0':
                backtrack(p, n-1)
            else:
                binary[0], binary[1] = binary[1], binary[0]
                backtrack(p, n-1)
                binary[0], binary[1] = binary[1], binary[0]
            p = p[:-1]
    
    if not n:
        return [0]
    ans = []
    binary = list('01')
    backtrack('', n)
    return ans

方法二：此题有规律，这个规律讲不太好，有点像之字形那种感觉，倒序的时候在最高位补1。就能满足每个数只变化一位的要求。

0   1   11  110
        10  111
            101
            100

start:      [0]  # [0]
i = 0:      [0, 1]  # [0, 1]
i = 1:      [0, 1, 3, 2]  # [00, 01, 11, 10]
i = 2:      [0, 1, 3, 2, 6, 7, 5, 4]  # [000, 001, 011, 010, 110, 111, 101, 100]

def grayCode(self, n: int) -> List[int]:
    ans = [0]
    for i in range(n):
        # ans += [x + pow(2, i) for x in reversed(ans)]
        ans += (x | 1<<i for x in reversed(ans))
    return ans

842. Split Array into Fibonacci Sequence

一串数组组成的字符串拆成斐波那契数列。原题

Input: "123456579"
Output: [123,456,579]

Input: "112358130"
Output: []
Explanation: The task is impossible.

ps: 此题第一天做的时候想了很久，提交了n个错误答案，后来第二天做的时候，20分钟就做出来了。

方法一：第一次AC的答案。需要注意几个点。首先只有当元素结果大于2才算数列；主循环中range(1, len(rest)+1)否则会丢失最后元素；因为0的存在，所以要考虑0不能作为数字的开头；最后题中要求每个数字要在int32范围内。224ms.

def splitIntoFibonacci(self, S: str) -> List[int]:
    
    def backtrack(p, rest):
        if not rest and len(p) > 2:
            ans.append(list(map(int, p)))
        for i in range(1, len(rest)+1):
            if len(p) < 2 or int(rest[:i])==int(p[-1])+int(p[-2]):
                if len(rest[:i]) > 1 and rest[0]=='0':
                    continue
                if int(rest[:i]) > 2**31-1:
                    continue
                backtrack(p+[rest[:i]], rest[i:])
    ans = []
    backtrack([], S)
    return ans[0] if ans else []

优化二：添加一个flag，在找到结果后返回。188ms, beats 26%.

def splitIntoFibonacci(self, S: str) -> List[int]:
    
    def backtrack(p, rest):
        # print(p, rest)
        if not rest and len(p) > 2:
            ans.append(list(map(int, p)))
            return True
        for i in range(1, len(rest)+1):
            if len(p) < 2 or int(rest[:i])==int(p[-1])+int(p[-2]):
                if len(rest[:i]) > 1 and rest[0]=='0':
                    break
                if int(rest[:i]) > 2**31-1:
                    break
                if backtrack(p+[rest[:i]], rest[i:]):
                    return True
        return False
    ans = []
    backtrack([], S)
    return ans[0] if ans else []

优化三：每个元素既然小于2**31-1那么，最长长度为10。在主循环中加入此条件可以提升到52ms。

def splitIntoFibonacci(self, S: str) -> List[int]:

    def backtrack(p, rest):
        if not rest and len(p) > 2:
            return list(map(int, p))
        for i in range(1, min(11, len(rest)+1)):
            to_add = rest[:i]
            if len(p) < 2 or int(to_add)==int(p[-1])+int(p[-2]):
                if len(to_add) > 1 and rest.startswith('0'):
                    break
                if int(to_add) > 2**31-1:
                    break
                seq = backtrack(p+[to_add], rest[i:])
                if seq:
                    return seq
        return []

    ans = backtrack([], S)
    return ans

优化4：当前两个数和已经为3位数时，下一个数没必要从1开始了。44ms。无论怎么提交都达不到迭代的40ms。猜测可能是递归栈的瓶颈了吧。

def splitIntoFibonacci(self, S: str) -> List[int]:

    def backtrack(p, rest):
        if not rest and len(p) > 2:
            p[:] = list(map(int, p))
            return True
        if len(p) >= 2:
            next_num = int(p[-1]) + int(p[-2])
            start = len(str(next_num))
        else:
            start = 1
        for i in range(start, min(11, len(rest)+1)):
            to_add = rest[:i]
            if len(p) < 2 or int(to_add)==next_num:
                if len(to_add) > 1 and rest.startswith('0'):
                    break
                if int(to_add) > 2**31-1:
                    break
                p.append(to_add)
                if backtrack(p, rest[i:]):
                    return True
                p.pop()
        return False
    ans = []
    backtrack(ans, S)
    return ans

方法二：迭代。

def splitIntoFibonacci(self, S: str) -> List[int]:
    
    for i in range(min(10, len(S))):
        a = S[:i+1]
        if a != '0' and a.startswith('0'): break
        a = int(a)
        for j in range(i+1, min(i+10, len(S))):
            b = S[i+1:j+1]
            if b != '0' and b.startswith('0'): break
            b = int(b)
            fib = [a, b]
            k = j + 1
            while k < len(S):
                nxt = fib[-2] + fib[-1]
                nxt_str = str(nxt)
                if nxt <= 2**31-1 and S[k:].startswith(nxt_str):
                    fib.append(nxt)
                    k += len(nxt_str)
                else:
                    break
            else:
                if len(fib) > 2:
                    return fib
    return []

46. Permutations

数组全排列。原题

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

方法一：recursively. 锁定头部法。思想为拿出一个数字作为头部，剩下的递归。

def permute(self, nums):
    return [[n] + p
            for i, n in enumerate(nums)
            for p in self.permute(nums[:i]+nums[i+1:])] or [[]]

方法二：到处插入法。

def permute(self, nums: 'List[int]') -> 'List[List[int]]':
    return nums and [p[:i] + [nums[0]] + p[i:]
                     for p in self.permute(nums[1:])
                     for i in range(len(nums))] or [[]]

方法二：iteratively. 思想为拿出一个数字插入到现有排序中的各个位置。

def permute(self, nums):
    ans = [[]]
    for n in nums:
        ans = [l[:i] + [n] + l[i:]
               for l in ans
               for i in range(len(l)+1)]
    return ans

47. Permutations II

全排列并去重。原题

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路：当然可以使用set来去重，或者考虑一种迭代的方式。

展开。拿着每个数字向上一个结果中插入到每一个位置。

def permuteUnique(self, nums):
    ans = [[]]
    for j, n in enumerate(nums):
        new_ans = []
        for l in ans:
            for i in range(len(l)+1):
                new_ans.append(l[:i]+[n]+l[i:])
                print('\t j {0} - {3} + [{2}] + {4}'.format(j, i, n, l[:i], l[i:]))
                # if i<len(l) and l[i]==n: break              #handles duplication
                if i<len(l) and l[i]==n: 
                    print('\t \t l[{}] == {}'.format(i, n))
                    break              #handles duplication
        ans = new_ans
        print('j {} afer inner ans {}'.format(j, ans))
    return ans

输入nums=[1, 2, 3]

	 j 0 - [] + [1] + []
j 0 afer inner ans [[1]]
	 j 1 - [] + [2] + [1]
	 j 1 - [1] + [2] + []
j 1 afer inner ans [[2, 1], [1, 2]]
	 j 2 - [] + [3] + [2, 1]
	 j 2 - [2] + [3] + [1]
	 j 2 - [2, 1] + [3] + []
	 j 2 - [] + [3] + [1, 2]
	 j 2 - [1] + [3] + [2]
	 j 2 - [1, 2] + [3] + []
j 2 afer inner ans [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]

理解一下是如何去重的，我们输入nums=[1, 2, 1]

	 j 0 - [] + [1] + []
j 0 afer inner ans [[1]]
	 j 1 - [] + [2] + [1]
	 j 1 - [1] + [2] + []
j 1 afer inner ans [[2, 1], [1, 2]]
	 j 2 - [] + [1] + [2, 1]
	 j 2 - [2] + [1] + [1]
	 	 l[1] == 1
	 j 2 - [] + [1] + [1, 2]
	 	 l[0] == 1
j 2 afer inner ans [[1, 2, 1], [2, 1, 1], [1, 1, 2]]
[[1, 2, 1], [2, 1, 1], [1, 1, 2]]

列表生成式整合。Stefan大神的写法。使用index来找非重复的临界值。

def permuteUnique(self, nums):
    ans = [[]]
    for n in nums:
        ans = [l[:i]+[n]+l[i:]
               for l in ans
               for i in range((l+[n]).index(n)+1)]
    return ans

递归也可以

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    return nums and [p[:i] + [nums[0]] + p[i:]
                     for p in self.permuteUnique(nums[1:])
                     for i in range((p+[nums[0]]).index(nums[0])+1)
                     ] or [[]]

1079. Letter Tile Possibilities

本来是一道回溯的题，结果测试用例过于简单，所以暴力法就解出来了。原题

1
2
3

Input: "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

def numTilePossibilities(self, tiles: str) -> int:
    from itertools import permutations
    n = len(tiles)
    return sum(len(set(permutations(tiles, i))) for i in range(1, n+1))

1415. The k-th Lexicographical String of All Happy Strings of Length n

列出第k个快乐字符串（a,b,c）组成并没有连续相同的字母。原题

方法一：回溯法。列出所有的值，排序索引。

def getHappyString(self, n: int, k: int) -> str:
    combine = []
    s = 'abc'
    
    def backtrack(cur, n):
        if n == 0:
            combine.append(cur)
            return
        for c in s:
            if not (cur and cur[-1]==c):
                backtrack(cur+c, n-1)
    
    backtrack('', n)
    combine.sort()
    return combine[k-1] if k <= len(combine) else ''

方法二：开始想的就是这种方法，后来想偏了，想用数学的方式直接求目标字符串，最后没有写出来。

def getHappyString(self, n: int, k: int) -> str:
    nxt = {'a': 'bc', 'b': 'ac', 'c': 'ab'} 
    q = collections.deque(['a', 'b', 'c'])
    while len(q[0]) != n:
        u = q.popleft()    
        for v in nxt[u[-1]]:
            q.append(u + v)
    return q[k - 1] if len(q) >= k else ''

1255. Maximum Score Words Formed by Letters

给定一些单词，每个字母有得分，不过每个字母用多少是有限制的。问最大得分是多少，一个典型的背包问题。原题

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23
Explanation:
Score  a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.

方法一：回溯。累加单词的分数可以提前退出递归。

def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
    self.ans, n = 0, len(words)
    wc = [Counter(w) for w in words]
    ws = [sum(v*score[ord(k)-ord('a')] for k, v in wc[i].items()) for i in range(n)]
    
    def dfs(i, s, left):
        if s + sum(ws[i:]) <= self.ans:
            return
        self.ans = max(self.ans, s)
        for j, wcnt in enumerate(wc[i:], i):
            if all(n <= left.get(c, 0) for c, n in wcnt.items()):
                dfs(j+1, s+ws[j], left-wcnt)
                
    dfs(0, 0, Counter(letters))
    return self.ans

方法二：这个和我一开始想的方法很像。

def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
    def backtrack(i, left):
        if i == len(words):
            return 0
        wc = Counter(words[i])
        if all(n<=left[c] for c, n in wc.items()):
            cur_score = sum(v*score[ord(k)-ord('a')] for k, v in wc.items())
            ans = max(cur_score + backtrack(i+1, left-wc), backtrack(i+1, left))
        else:
            ans = backtrack(i+1, left)
        return ans
    return backtrack(0, Counter(letters))

1239. Maximum Length of a Concatenated String with Unique Characters

最长的不重复的字符串组合。原题

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

方法一：回溯法。

def maxLength(self, arr: List[str]) -> int:
    def dfs(i, seen):
        if i == len(arr):
            return 0 
        if set(arr[i]) & seen or len(set(arr[i]))!=len(arr[i]):
            ans = dfs(i+1, seen)
        else:
            ans = max(len(arr[i]) + dfs(i+1, seen|set(arr[i])), dfs(i+1, seen))
        return ans
        
    return dfs(0, set())

方法二：Lee215的解法。append的方式，会将每步累加的追加的ans中。

def maxLength(self, arr: List[str]) -> int:
    ans = [set()]
    for a in arr:
        if len(set(a)) != len(a):continue
        a = set(a)
        for c in ans[:]:
            if a & c: continue
            ans.append(a | c)
    return max(len(a) for a in ans)

51. N-Queens

著名的N皇后问题，将N个皇后摆在N*N的棋盘中，直线，斜线不能同时存在2个皇后。问所有的摆放位置。原题

方法一：调了一次就AC了。记录第一次AC的方法。

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

    l_dig = [False] * (n*2-1)
    r_dig = [False] * (n*2-1)
    row = [False] * n
    col = [False] * n
        
    def backtrack(i, j, k, g):
        # print(i, j, k, g)
        row[i] = True
        col[j] = True
        l_dig[i+j] = True
        r_dig[j-i+n-1] = True
        g[i][j] = 'Q'
        if not k-1:
            ans.append([''.join(row) for row in g])
        for x in range(i+1, n):
            if not row[x]:
                for y in range(n):
                    if not col[y]:
                        if not l_dig[x+y] and not r_dig[y-x+n-1]:
                            backtrack(x, y, k-1, g)
        row[i] = False
        col[j] = False
        l_dig[i+j] = False
        r_dig[j-i+n-1] = False
        g[i][j] = '.'
                        
    ans = []
    for j in range(n):
        g = [['.']*n for _ in range(n)]
        backtrack(0, j, n, g)
    return ans

方法二：row是不必要的，因为遍历行是不会有重复的。

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

    l_dig = [False] * (n*2-1)
    r_dig = [False] * (n*2-1)
    col = [False] * n
        
    def backtrack(i, j, k, g):
        # print(i, j, k, g)
        col[j] = l_dig[i+j] = r_dig[j-i+n-1] = True
        g[i][j] = 'Q'
        if not k-1:
            ans.append([''.join(row) for row in g])
        for x in range(i+1, n):
            for y in range(n):
                if not col[y]:
                    if not l_dig[x+y] and not r_dig[y-x+n-1]:
                        backtrack(x, y, k-1, g)
        col[j] = l_dig[i+j] = r_dig[j-i+n-1] = False
        g[i][j] = '.'
                        
    ans = []
    for j in range(n):
        g = [['.']*n for _ in range(n)]
        backtrack(0, j, n, g)
    return ans

方法三：上述两种方法，用时800ms，此方法52ms，直接以行为单位进行回溯。

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

    l_dig = [False] * (n*2-1)
    r_dig = [False] * (n*2-1)
    col = [False] * n
        
    def backtrack(i, g):
        # print(i, j, k, g)
        if i == n:
            ans.append(list(g))
            return 
        
        for j in range(n):
            if not col[j] and not l_dig[i+j] and not r_dig[j-i+n-1]:
                row = '.'*j + 'Q' + '.'*(n-j-1)
                g.append(row)
                col[j] = l_dig[i+j] = r_dig[j-i+n-1] = True
                backtrack(i+1, g)
                col[j] = l_dig[i+j] = r_dig[j-i+n-1] = False
                g.pop()
                        
    ans = []
    backtrack(0, [])
    return ans

52. N-Queens II

和上边一样的N皇后问题，要求最后有多少种。原题

方法一：不再需要一个数组来记录棋盘了，只需要计数就行。然后通过一个数组标记每行的棋子的纵坐标。而且无需重置，因为值会覆盖之前的。本质上还是回溯方法。

def totalNQueens(self, n: int) -> int:
    rows = [-1] * n
    
    def valid(k):
        for i in range(k):
            if rows[i]==rows[k] or abs(rows[k]-rows[i]) == k-i:
                return False
        return True
    
    def dfs(i):
        if i == n: 
            nonlocal ans
            ans += 1
            return
        for j in range(n):
            rows[i] = j
            if valid(i):
                dfs(i+1)
    
    ans = 0
    dfs(0)
    return ans

方法二：位运算，空间上节省了一个一维数组，虽然数组长度不会很长。时间上快了一倍。

def totalNQueens(self, n: int) -> int:

    def dfs(n, row=0, col=0, ld=0, rd=0, bits=0):
        if row >= n: 
            nonlocal count
            count += 1
            return
        # col, ld, rd 中1表示不能放置，0表示可以放置
        bits = (~(col | ld | rd)) & ((1 << n) - 1)
        # bits 表示剩余的皇后的列位置，也就是说某位为1，表示这一列的皇后还没有放
        while bits:   
            p = bits & -bits   # 保留最后一位1，其余置为0
            bits = bits & (bits - 1)  # 去掉最后一位1
            dfs(n, row+1, col|p, (ld|p) << 1, (rd|p) >> 1, bits)

    count = 0
    dfs(n)
    return count

37. Sudoku Solver

解9*9的数独。原题

方法一：首次AC的方法，嗨呀，递归调用时忘记写return True了，调了半天。

def solveSudoku(self, g: List[List[str]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    row = [[True]*9 for i in range(9)]        
    col = [[True]*9 for i in range(9)]
    sub = [[True]*9 for i in range(9)]
    to_add = []
    for i in range(9):
        for j in range(9):
            if g[i][j] != '.':
                d = int(g[i][j]) - 1
                row[i][d] = col[j][d] = sub[i//3*3+j//3][d] = False
            else:
                to_add.append((i, j))

    def backtrack():
        if not to_add: 
            return True
        i, j = to_add.pop()
        for d in range(9):
            if row[i][d] and col[j][d] and sub[i//3*3+j//3][d]:
                g[i][j] = str(d+1)
                row[i][d] = col[j][d] = sub[i//3*3+j//3][d] = False
                if backtrack():
                    return True
                g[i][j] = '.'
                row[i][d] = col[j][d] = sub[i//3*3+j//3][d] = True
        to_add.append((i, j))
        return False

    backtrack()

980. Unique Paths III

二维数组中有0，1，2，-1四种格子，要求从1开始走到2，经过所有的0，一共有多少种走法。

方法一：回溯法，思路很清晰，很快就写出来了，方向变量写错了调了半天。只需要关注0的个数就行。有优化的地方，因为1和2只有一个，所以可以先遍历一次找出0个个数和1的位置。

def uniquePathsIII(self, g: List[List[int]]) -> int:
    M, N = len(g) , len(g[0])
    f = sum(g, [])
    zero = f.count(0)
    self.ans = 0
    
    def bf(i, j, n):
        ori = g[i][j]    
        if ori == 2:
            if n==zero+2:
                self.ans += 1
            return 
        g[i][j] = -1
        for x, y in ((i+1, j), (i, j+1), (i-1, j), (i, j-1)):
            if 0<=x<M and 0<=y<N and g[x][y] in (0, 2):
                bf(x, y, n+1)
        g[i][j] = ori
    
    for i in range(M):
        for j in range(N):
            if g[i][j] == 1:
                bf(i, j, 1)
                
    return self.ans

491. Increasing Subsequences

求一个数组的所有的长度2以上的递增子序列。

方法一：联系了几道题，求最大长度的是用的dp，不适合这个。这里发现和subsets的组合有点像。于是用了78题中的方法二。因为数组本身最大也就15长度，所以方法并不很耗时。

def findSubsequences(self, nums: List[int]) -> List[List[int]]:
    ans = [[]]        
    for num in nums:
        ans += [pre+[num] for pre in ans if not pre or pre[-1]<=num]
    return list({tuple(a) for a in ans if len(a)>=2})

方法二：我想用90的方法直接去重，试了一下，发现90题依赖数组有序才能去重，所以这里并不适用。只能最后通过转化tuple，set再去重。效率只有方法一的一半。

def findSubsequences(self, nums: List[int]) -> List[List[int]]:
    
    def dfs(i, m, p):
        if not m:
            ans.append(p[:])
            return
        for j in range(i, n):
            d = nums[j]
            if not p or d >= p[-1]:
                p.append(d)
                dfs(j+1, m-1, p)
                p.pop()
    
    n, ans = len(nums), []
    [dfs(0, i, []) for i in range(2, n+1)]
    return list({tuple(a) for a in ans})

方法三：Stefan的方法，我想的就差了一步，ans可以直接用set。

def findSubsequences(self, nums: List[int]) -> List[List[int]]:
    ans = {()}
    for num in nums:
        ans |= {pre+(num, ) for pre in ans if not pre or pre[-1]<=num}
    return [a for a in ans if len(a)>=2]

面试题 08.09. 括号

求n对括号的合法组合。

方法一：回溯，我的方法。

def generateParenthesis(self, n: int) -> List[str]:

    def backtrack(l, r, p):
        if not l and not r: 
            ans.append(''.join(p))
            return 
        if l:
            p.append('(')
            backtrack(l-1, r, p)
            p.pop()
        if r and r>l:
            p.append(')')
            backtrack(l, r-1, p)
            p.pop()

    ans = []
    backtrack(n, n, [])
    return ans

方法二：大神的方法，学习了，使用and代替if。

def generateParenthesis(self, n: int) -> List[str]:

    ans = []
    def f(l, r, s):
        l == r == n and ans.append(s)
        l < n and f(l + 1, r, s + '(')
        r < l and f(l, r + 1, s + ')')
    f(0, 0, '')
    return ans

1655. Distribute Repeating Integers

分配重复的数字，根据`quantity`中每个顾客的需求，给每个人分配`quantity[i]`个相同的元素。

Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.
Input: nums = [1,1,1,1,1], quantity = [2,3]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].

方法一：暴力回溯法。作为竞赛的4题没有做上来。比赛的时候想用一种贪心的方式来做，这样做是不对的。这是Lee215竞赛时的方法。

def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
    cnts = sorted(Counter(nums).values())
    fail = {}
    N = len(quantity)
    
    def backtrack(state, i):
        if i == N:
            return True
        t = tuple(state)
        if t in fail:
            return False
        x = quantity[i]
        for j, v in enumerate(state):
            if j>0 and state[j-1]==v:
                continue
            if v < x:
                continue
            state[j] -= x
            if backtrack(sorted(state), i+1):
                return True
            state[j] += x
        fail[t] = False
        return False
    
    return backtrack(cnts, 0)

1718. Construct the Lexicographically Largest Valid Sequence

给你一个整数 n ，请你找到满足下面条件的一个序列：

整数 1 在序列中只出现一次。
2 到 n 之间每个整数都恰好出现两次。
对于每个 2 到 n 之间的整数 i ，两个 i 之间出现的距离恰好为 i 。
序列里面两个数 a[i] 和 a[j] 之间的距离，我们定义为它们下标绝对值之差 |j - i| 。

请你返回满足上述条件中字典序最大的序列。

1
2
3

输入：n = 3
输出：[3,1,2,3,2]
解释：[2,3,2,1,3] 也是一个可行的序列，但是 [3,1,2,3,2] 是字典序最大的序列。

方法一：比赛时没时间做，思路是正确的，有一个判断很关键，没有这个判断代码将会超时。里面有贪心的思想，优先拿最大的数。

def constructDistancedSequence(self, n: int) -> List[int]:

    can = list(range(1, n+1))
    res = [-1] * (n*2 - 1)

    def backtrack(i, left):
        if not left:
            return True
        if res[i] != -1:					# 没有这个优化，代码将会超时。
            return backtrack(i+1, left)
        for j in range(len(left)-1, -1, -1):
            d = left[j]
            r = i if d==1 else i+d
            if r<len(res) and res[r]==-1:
                res[i] = res[r] = d
                if backtrack(i+1, left[:j]+left[j+1:]):
                    return True
                res[i] = res[r] = -1

    backtrack(0, can)
    return res

1723. Find Minimum Time to Finish All Jobs

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的工作时间是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的最大工作时间得以最小化。

1
2
3

输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。

方法一：竞赛时搜了一下，以为是NP背包问题被吓住了，其实给定的范围可以用回溯剪枝的方式来做。总共有三个优化点。其中第二点比较难想。1. 可以按照时长最多的倒序分配给每个工人；2.让某个工人不干活的次数只有一次，比如以[3,2,3],k=3为例，[32,3,0]与[32,0,3]是重复的，后者可以提前终止；如果当前结果过大了，就不用再继续了。2852ms.

def minimumTimeRequired(self, A: List[int], k: int) -> int:
    n = len(A)
    A.sort(reverse=True) # opt 1
    self.res = sum(A)
    count = [0] * k

    def dfs(i):
        if i == n:
            self.res = min(self.res, max(count))
            return
        for j in range(k):
            if count[j] + A[i] < self.res: # opt 3
                count[j] += A[i]
                dfs(i + 1)
                count[j] -= A[i]
            if count[j] == 0: 
                break # opt 2
    dfs(0)
    return self.res

方法二：二分法，这个方法简直超神，用二分法来确定这个容量的值。耗时44ms。

def minimumTimeRequired(self, A: List[int], k: int) -> int:
    n = len(A)
    A.sort(reverse=True) # opt 1
    
    def dfs(i):
        if i == n:
            return True
        for j in range(k):
            if cap[j] >= A[i]:
                cap[j] -= A[i]
                if dfs(i + 1): return True
                cap[j] += A[i]
            if cap[j] == mid: break # opt 2
        return False
    
    left, right = max(A), sum(A)
    while left < right:
        mid = (left+right) >> 1
        cap = [mid] * k
        if dfs(0):
            right = mid
        else:
            left = mid + 1
    return left

93. Restore IP Addresses

恢复IP地址。原题

131. Palindrome Partitioning

回文串切分。原题

77. Combinations

实现组合。原题

39. Combination Sum

和77类似，找出和为指定数值的组合，候选数字可以重复使用。原题

40. Combination Sum II

组合求和，和39类似，区别在于候选数字中可能有重复数字，但每个数字只能使用一次。原题

216. Combination Sum III

组合求和，从1~9选出k个不重复的数，和为n。原题

78. Subsets

输出给定无重复集合的子集组合。原题

90. Subsets II

和78类似，区别在于给定的数组有重复元素。原题

79. Word Search

矩阵中的路径。原题

200. Number of Islands

小岛的个数。原题

1254. Number of Closed Islands

和200类似，但是与边界相连的岛不能算了。原题

130. Surrounded Regions

将四周被包围的O翻转成X，边缘不算包围。原题

417. Pacific Atlantic Water Flow

太平洋大西洋水流向，假设陆地上可以沿着高度不高于的地方流淌，求能同时流入两个海洋的陆地坐标。原题

526. Beautiful Arrangement

完美安排，给定1~N的数字，生成一种排列，是第i位的数字能被i整除，或者i能被第i位的数字整除，索引从1开始。原题

22. Generate Parentheses

生成n对合法的括号。原题

89. Gray Code

灰码问题。给定一个n表示n位。从0开始每次改变一个位的数字，产生所有的组合。原题

842. Split Array into Fibonacci Sequence

一串数组组成的字符串拆成斐波那契数列。原题

46. Permutations

数组全排列。原题

47. Permutations II

全排列并去重。原题

1079. Letter Tile Possibilities

本来是一道回溯的题，结果测试用例过于简单，所以暴力法就解出来了。原题

1415. The k-th Lexicographical String of All Happy Strings of Length n

列出第k个快乐字符串（a,b,c）组成并没有连续相同的字母。原题

1255. Maximum Score Words Formed by Letters

给定一些单词，每个字母有得分，不过每个字母用多少是有限制的。问最大得分是多少，一个典型的背包问题。原题

1239. Maximum Length of a Concatenated String with Unique Characters

最长的不重复的字符串组合。原题

51. N-Queens

著名的N皇后问题，将N个皇后摆在N*N的棋盘中，直线，斜线不能同时存在2个皇后。问所有的摆放位置。原题

52. N-Queens II

和上边一样的N皇后问题，要求最后有多少种。原题

37. Sudoku Solver

解9*9的数独。原题

980. Unique Paths III

二维数组中有0，1，2，-1四种格子，要求从1开始走到2，经过所有的0，一共有多少种走法。

491. Increasing Subsequences

求一个数组的所有的长度2以上的递增子序列。

面试题 08.09. 括号

求n对括号的合法组合。

1655. Distribute Repeating Integers

分配重复的数字，根据quantity中每个顾客的需求，给每个人分配quantity[i]个相同的元素。

1718. Construct the Lexicographically Largest Valid Sequence

1723. Find Minimum Time to Finish All Jobs

将四周被包围的`O`翻转成`X`，边缘不算包围。原题

分配重复的数字，根据`quantity`中每个顾客的需求，给每个人分配`quantity[i]`个相同的元素。