晨曦微光
0%

回溯算法类题目

Veröffentlicht am in

一、综述

回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。

二、回溯算法思路

所谓Backtracking都是这样的思路：

在当前局面下，你有若干种选择。

那么尝试每一种选择。

如果已经发现某种选择肯定不行（因为违反了某些限定条件），就返回；

如果某种选择试到最后发现是正确解，就将其加入解集

所以你思考递归题时，只要明确三点就行：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。即“ORT原则”。

比如对于括号生成这道题来说：

对于这道题，在任何时刻，你都有两种选择：

  1. 加左括号。
  2. 加右括号。

同时有以下限制：

  1. 如果左括号已经用完了，则不能再加左括号了。
  2. 如果已经出现的右括号和左括号一样多，则不能再加右括号了。因为那样的话新加入的右括号一定无法匹配。

结束条件是：
左右括号都已经用完。

结束后的正确性：
左右括号用完以后，一定是正确解。因为1. 左右括号一样多，2. 每个右括号都一定有与之配对的左括号。因此一旦结束就可以加入解集（有时也可能出现结束以后不一定是正确解的情况，这时要多一步判断）。

递归函数传入参数：
限制和结束条件中有“用完”和“一样多”字样，因此你需要知道左右括号的数目。
当然你还需要知道当前局面sublist和解集res。

三、例题

1. 电话号码的组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

img

示例:

1
2
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

思路：

这个就是标准的回溯算法了。

helper()函数，满足就res.append()，不满足就继续往下遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        lookup = {'2':['a','b','c'],
                   '3':['d','e','f'],
                   '4':['g','h','i'],
                   '5':['j','k','l'],
                   '6':['m','n','o'],
                   '7':['p','q','r','s'],
                   '8':['t','u','v'],
                   '9':['w','x','y','z']}
        
        if not digits:
            return []
        n = len(digits)
        res = []
        def helper(i,tmp):
            if i == n:
                res.append(tmp)
                return
            for al in lookup[digits[i]]:
                helper(i+1,tmp+al)
        helper(0,"")
        return res

2. 括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路：

很明显的回溯算法。

为什么要判断left_p<right_p：因为在任意位置，左括号的数量是大于等于右括号的数量的。如果left<right，说明左括号小于右括号，则不满足。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        
        def helper(left_p,right_p,tmp):
            if left_p == n and right_p == n:
                res.append(tmp)
                return
            if left_p > n or right_p > n or left_p < right_p:
                return
            helper(left_p+1,right_p,tmp+'(')
            helper(left_p,right_p+1,tmp+')')
        helper(0,0,"")
        return res

3. 解数独

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

img

一个数独。

img

答案被标成红色。

Note:

  • 给定的数独序列只包含数字 1-9 和字符 '.' 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

思路：

经典的回溯算法。

对于每一个为’.’的点都从1走到9，如果valid就继续走，如果不valid就立马返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        self.backtrack(board)
        
    def backtrack(self,board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for c in '123456789':
                        if self.isPointValid(board,i,j,c):
                            board[i][j] = c
                            if self.backtrack(board):
                                return True
                            else:
                                board[i][j] = '.'
                    return False
        return True
        
    def isPointValid(self,board,x,y,c):
        for i in range(9):
            if board[i][y] == c:
                return False
            if board[x][i] == c:
                return False
            if board[(x//3)*3+i//3][(y//3)*3+i%3] == c:
                return False
        return True

4. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

思路：

通过这道题，我们可以得到回溯算法的模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        n = len(candidates)
        res = []
        
        def helper(i,tmp_sum,tmp_list):
            if i == n or tmp_sum > target:
                return
            if tmp_sum == target:
                res.append(tmp_list)
                return
            for j in range(i,n):
                if tmp_sum + candidates[j] > target:
                  	 break
                helper(j,tmp_sum + candidates[j],tmp_list + [candidates[j]])
        helper(0,0,[])
        return res

5. 组合总和2

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

  • 所有数字（包括目标数）都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

思路：

这道题和上一题一样，也是回溯，只不过区别在于，回溯的时候，跳过相同数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        n = len(candidates)
        res = []
        def helper(i,tmp_sum,tmp):
            if tmp_sum == target:
                res.append(tmp)
                return
            for j in range(i,n):
                if tmp_sum + candidates[j] > target:
                    break
                if j > i and candidates[j] == candidates[j-1]:
                    continue
                helper(j+1,tmp_sum+candidates[j],tmp+[candidates[j]])
        helper(0,0,[])
        return res

6. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路：

这样的题就很习惯了，终止条件也可以为not nums

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        n = len(nums)
        def helper(nums,tmp):
            if len(tmp) == n:
                res.append(tmp)
            for i in range(len(nums)):
                helper(nums[:i]+nums[i+1:],tmp+[nums[i]])
        helper(nums,[])
        return res

7. 全排列2

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路：

和上一题一样的思路，只不过要跳过重复的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        n = len(nums)
        visited = set()
        def helper(nums,tmp):
            if len(tmp) == n:
                res.append(tmp)
                return
            for i in range(len(nums)):
                if i in visited or (i>0 and i-1 not in visited and nums[i] == nums[i-1]):
                    continue
                visited.add(i)
                helper(nums,tmp+[nums[i]])
                visited.remove(i)
        helper(nums,[])
        return res

当然也有别的回溯的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) == 0:
            return []
        if len(nums) == 1:
            return [nums]
        
        res = []
        for i in range(len(nums)):
            prefix = nums[i]
            rest = nums[:i]+nums[i+1:]
            for j in self.permuteUnique(rest):
                if [prefix] +j not in res:
                    res.append([prefix] + j)
        return res

8. N皇后

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

img

上图为 8 皇后问题的一种解法。

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

思路：

标准的回溯思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        res = []
        s = '.' * n
        def helper(i,tmp,col,z_dia,f_dia):
            if i  == n:
                res.append(tmp)
                return
            for j in range(n):
                if j not in col and (i+j) not in z_dia and (i-j) not in f_dia:
                    helper(i+1,tmp+[s[:j]+'Q'+s[j+1:]],col | {j},z_dia | {i+j},f_dia | {i-j})
        helper(0,[],set(),set(),set())
        return res

9. N皇后2

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

img

上图为 8 皇后问题的一种解法。

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.res = 0
        def helper(i,col,z_dia,f_dia):
            if i  == n:
                return True
            for j in range(n):
                if j not in col and (i+j) not in z_dia and (i-j) not in f_dia:
                    if helper(i+1,col | {j},z_dia | {i+j},f_dia | {i-j}):
                        self.res += 1
            return False
        helper(0,set(),set(),set())
        return self.res

10. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

思路：

很标准的回溯模板了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        n = len(nums)
        def helper(i,tmp):
            res.append(tmp)
            for j in range(i,n):
                helper(j+1,tmp+[nums[j]])
        helper(0,[])
        return res

11. 子集2

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

思路：

很标准的回溯算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        def helper(i,tmp):
            res.append(tmp)
            for j in range(i,len(nums)):
                if j > i and nums[j] == nums[j-1]:
                    continue
                helper(j+1,tmp+[nums[j]])
        helper(0,[])
        return res