发表更新刷题11 分钟读完 (大约1587个字)

回溯类题目

解决一个回溯问题，实际上就是一个决策树的遍历过程。需要考虑三个问题

1、路径：就是已经做出的选择

2、选择列表：就是当前可以做出的选择

3、结束的条件：就是到达决策树底层，无法在做选择的条件。

算法框架：

1
2
3
4
5
6
7
8
9
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
    	return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择/回溯

17. 电话号码的字母组合

这是一个全排列问题

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
class Solution:
    def letterCombinations(self, digits: str) ->list:
        ch_dict = {
            "2": "abc",
            "3": "def",
            "4":"ghi",
            "5": "jkl",
            "6":"mno",
            "7":"pqrs",
            "8":"tuv",
            "9":"wxyz"
        }
        results = []

        
        for dig in digits:
            temp_list = []
            for ch  in ch_dict[dig]:
                temp_list.append(ch) # 添加字符
            print(temp_list)
            if len(results) == 0: 
                results = temp_list
            else:
                temp_list2 = []
                for res in results:
                    for t_ch in temp_list:
                        temp_list2.append(res+t_ch)    
                results = temp_list2

        return results

官方解法

首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。

回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。

该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。

然后进行回退操作，遍历其余的字母排列。

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
def officeletterCombinations(self, digits: str) ->list:
    ch_dict = {
        "2": "abc",
        "3": "def",
        "4":"ghi",
        "5": "jkl",
        "6":"mno",
        "7":"pqrs",
        "8":"tuv",
        "9":"wxyz"
    }
    combination = list()
    combinations = list()
    def backtrack(index: int):
        # 这里是一个隐含的限制条件，组合的长度和输入的长度一样
        if index == len(digits):
            combinations.append("".join(combination))
        else:
            digit = digits[index] # 获取当前的数组

            # 遍历当前数字对应的字母
            for letter in ch_dict[digit]: 
                combination.append(letter)
                backtrack(index+1) # 遍历下一个数字
                combination.pop()

    backtrack(0)
    return combinations

22. 括号生成

官方解法

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
class Solution:
    def generateParenthesis(self, n: int) -> list:

        results = []
        res = []

        def backtract(left:int,right:int):
            print("-->",res)
            if len(res) == 2*n:
                results.append(''.join(res))
                return
            print("---->")
            if left < n:
                res.append("(")
                backtract(left+1,right) # 左括号数目加1
                res.pop() # 当前的选择满足后，弹出左括号，进行回溯
            print("===========>")
            if right < left: # 添加右括号
                res.append(")")
                backtract(left,right+1)
                res.pop()
        backtract(0,0)
        
        return results

51. N 皇后 - 力扣

参考题解

N皇后，经典回溯算法（图文详解） - N 皇后 - 力扣（LeetCode） (leetcode-cn.com)

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
51
52
53
54
class Solution {
    public List<String> construct(char[][] chess) {
        List<String> path = new ArrayList<>();
        for (int i = 0; i < chess.length; i++) {
            path.add(new String(chess[i]));
        }
        return path;
    }
    public boolean valid(char [][]chess,int row,int col){
        //判断当前列有没有皇后,因为他是一行一行往下走的，
        //我们只需要检查走过的行数即可，通俗一点就是判断当前
        //坐标位置的上面有没有皇后
        // 检查当前列有没有冲突的，因为他行一直是往前的
        for(int i=0; i<row;i++){
            if(chess[i][col] == 'Q') return false;
        }
        // 判断当前坐标的右上角有没有皇后
        for(int i = row-1,j=col+1;i>=0 && j<chess.length;i--,j++){
            if(chess[i][j] == 'Q') return false;
        }
        // 判断当前坐标的左上角有没有皇后
        for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){
            if(chess[i][j] == 'Q') return false;
        }
        return true;
    }

    public void backtract(List<List<String>> res,char[][] chess,int row){
        if(row == chess.length){
            res.add(construct(chess));
            return;
        }
        for(int col=0; col < chess.length;col++){
            // 对当前位置进行判断，排除不合法的选择
            if(valid(chess, row, col)){

                // 做选择
                chess[row][col] = 'Q';
                // 进行下一行决策
                backtract(res, chess, row+1);
                // 撤销选择
                chess[row][col]='.';
            }
        }
    }
    public List<List<String>> solveNQueens(int n) {
        char[][] chess = new char[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                chess[i][j] = '.';
        List<List<String>> res = new ArrayList<>();
        backtract(res, chess, 0);
        return res;
    }

39. 组合总和

参考用户：powcai - 力扣（LeetCode） (leetcode-cn.com)

题解参考自评论区

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:
    def combinationSum(self, candidates: list(), target: int):
        res_s = list()
        res = list()

        n = len(candidates)
        candidates = sorted(candidates)

        def backtract(i):
            # 满足结束的条件
            if sum(res) == target:
                res_s.append(res.copy()) # 这里使用copy是因为，后面弹出会影响
             
                return
            
            # 做选择
            for j in range(i,n):
                if sum(res) + candidates[j]>target:
                    break 
                res.append(candidates[j])           
                backtract(j) # 继续从当前的节点开始遍历
                # 撤销选择
                res.pop(-1)

        backtract(0)
        # print(res_s)
        return res_s

77. 组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def combine(self, n: int, k: int):
        ress = []
        res = []

        def backtract(j):
            # 结束的条件
            if len(res) == k:
                ress.append(res.copy())
                return
            for i in range(j,n+1):
                if i in res:
                    print(res,i)
                    break
                # 做选择
                res.append(i)
                # 路径，选择列表
                backtract(j+1)
                # 撤销选择
                res.pop()
        backtract(1)
        return ress

40. 组合总和 II

本题的关键在于去重，参考评论区

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
class Solution:
    def combinationSum2(self, candidates: list(), target: int):
        ress = []
        res = []
        candidates = sorted(candidates)
        n = len(candidates)
        def backtract(i):
            if sum(res) == target and res not in ress:
                ress.append(res.copy())
                return
            for j in range(i,n):
                # print(i,n,target)
                # print(sum(res) + candidates[j] )
                # 如果索引不同的位置，节点相同则跳过，去重
                if j != i and candidates[j] == candidates[j-1]:
                    continue
                if sum(res) + candidates[j] > target:
                    break
                # print("---s")
                res.append(candidates[j])
                # print("res",res)
                backtract(j+1) # 从下一个节点开始
                res.pop() 

        backtract(0)
        return ress

46. 全排列

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
class Solution:
    def permute(self, nums: list):
        ress = []
        res = []
        n = len(nums)

        def backtract(i):
            # 结束条件
            if len(res) == n :
                ress.append(res.copy())
                return
            for j in range(n):
                # print('-',j)
                # 排除不合法选择
                if nums[j]  in res:
                #     print(res,nums[j])
                    continue
                # 做选择
                res.append(nums[j])
                # 下一行决策
                backtract(j+1)
                # 撤销选择
                res.pop()
        backtract(0)
        return ress

47. 全排列 II

参考自评论区

树层上去重(used[i - 1] == false)，的树形结构如下：

image-20210805173441314

树枝上去重（used[i - 1] == true）的树型结构如下：

image-20210805173513948 
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 permuteUnique(self, nums):
        ress = list()
        res = list()
        n = len(nums)
        nums = sorted(nums)
        used = [0] * n
        def backtrack():
            if len(res) == n:
                # print("--->",res)
                ress.append(res.copy())
                return
            
            for i in range(n):
                if not used[i]: # 当前这个没有访问过
                    # 如果当前这个和前一个一样，并且前一个也没有访问过，就跳出
                    # used[i - 1] == false，说明同一树层nums[i - 1]使用过
                    if i>0 and nums[i] == nums[i-1] and  used[i-1] == False:
                        continue
                    used[i] = 1
                    res.append(nums[i])
                    # print("===>",res)
                    backtrack()
                    res.pop()
                    used[i] = 0
        
        backtrack()
        return ress

回溯类题目

http://example.com/2021/08/02/回溯题目/

作者

bd160jbgm

发布于

2021-08-02

更新于

2021-08-05

许可协议

#

喜欢这篇文章？打赏一下作者吧

关注我

链接

分类

最新文章

标签

BFS3
DFS3
Java面经1
algorithm4
android1
bfs2
c++9
dfs7
dp1
dpLearning13
java1
jvm9
ordered-map1
python8
spring6
sql3
tools16
二分查找1
二叉树13
位运算10
傻屌题1
分治2
分治算法2
动态规划6
双指针7
哈希1
哈希表2
回溯5
堆2
堆排序1
多线程1
字符串5
总结1
找规律2
指针1
排序9
数字1
数据库1
数组9
最短路径1
查找2
栈9
树12
测试6
测试知识1
滑动窗口1
自动机1
计算机基础2
计算机网络1
计算机网络基础1
论文阅读10
设计1
贪心算法3
较难13
递归6
链表14
队列1
需要review8
面试记录1
×