Z.H.Chen's Blog
0%

LeetCode——回溯算法的经典问题

发表于 分类于 ， Valine：
589 1 分钟

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

在这里插入图片描述
示例：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
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
32
33
34
35
36
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "" :
            return []
        #数字字母映射表
        mapping = {
            '2' : 'abc', 
            '3' : 'def', 
            '4' : 'ghi', 
            '5' : 'jkl', 
            '6' : 'mno', 
            '7' : 'pqrs', 
            '8' : 'tuv', 
            '9' : 'wxyz'
        }
        res = []
        res_str = []

        mapping_digits = []
        for i in range(len(digits)) :
            mapping_digits.append(mapping[digits[i]])

        def backtracking(res_str, index) :
            #递归终止条件
            if len(res_str) == len(digits) :
                res.append("".join(res_str))
                return 
            
            for i in range(len(mapping_digits[index])) :
                res_str.append(mapping_digits[index][i])
                #回溯
                backtracking(res_str, index + 1)
                #撤销
                res_str.pop()
        backtracking(res_str, 0)
        return res

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例：

1
2
3
4
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。
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
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        res_temp = []

        def backtracking(candidates, target, res_temp, startIndex) :
            #递归终止条件
            if sum(res_temp) == target :
                res.append(res_temp[:])
                return
            
            #应满足的条件
            if sum(res_temp) > target :
                return 

            for col in range(startIndex, len(candidates)) :
                #剪枝
                if sum(res_temp) + candidates[col] > target :
                    return 
                res_temp.append(candidates[col])
                #回溯
                backtracking(candidates, target, res_temp, col)
                #撤销
                res_temp.pop()
        candidates = sorted(candidates)
        backtracking(candidates, target, res_temp, 0)

        return res

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以按任意顺序 返回答案。

示例：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res_temp = []
        res = []

        def backtracking(res_temp) :
            if len(res_temp) == len(nums) :
                res.append(res_temp[ : ])
                return 
                
            for i in range(0, len(nums)) :
                #不能含有相同元素
                if nums[i] in res_temp :
                    continue
                res_temp.append(nums[i])
                backtracking(res_temp)
                res_temp.pop()
        backtracking(res_temp)
        return res

51. N 皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例：
在这里插入图片描述

1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
    def solveNQueens(self, n: int):
        chess = [['.'] * n for _ in range(n)]
        if not n:
            return []
        res = []

        def IsVaild(chess, row, col, n):
            # 判断列
            for i in range(n):
                if chess[i][col] == 'Q':
                    return False

            # 判断左对角线
            i = row -1
            j = col -1
            while i >= 0 and j >= 0:
                if chess[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
                
            # 判断右对角线
            i = row - 1
            j = col + 1
            while i>=0 and j < len(chess):
                if chess[i][j] == 'Q':
                    return False
                i -= 1
                j += 1
            return True

        def backtracking(chess, row, n):
            #递归终止条件
            if row == n:
                res_temp = []
                for result in chess:
                    res_temp.append("".join(result))
                res.append(res_temp)

            for col in range(n):
                if not IsVaild(chess, row, col, n):
                    continue
                chess[row][col] = 'Q'
                # print(chess)
                backtracking(chess, row + 1, n)
                chess[row][col] = '.'

        backtracking(chess, 0, n)
        return res

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

示例：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        res_temp = []

        def backtracking(res_temp, k, index) :
            #终止条件
            if len(res_temp) == k :
                res.append(res_temp[ : ])
                return 
            
            for i in range(index, n + 1) :
                #剪枝操作
                if (n + 1) - i + len(res_temp) < k :
                    return 
                res_temp.append(i)
                backtracking(res_temp, k, i + 1)
                res_temp.pop()

        backtracking(res_temp, k, 1)
        return res

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        res_temp = []
        nums = sorted(nums)

        def backtracking(res_temp, startIndex) :
            res.append(res_temp[ : ])
            for i in range(startIndex, len(nums)) :
                res_temp.append(nums[i])
                backtracking(res_temp, i + 1)
                res_temp.pop()

        backtracking(res_temp, 0)
        return res