Okii's blog

仅作为记录自己的学习过程

0%

Leetcode 回溯—组合篇

发表于 分类于
本文字数： 4.5k 阅读时长 ≈ 8 分钟

Leetcode刷题记录——回溯组合篇

Leetcode77 组合

对于仅使用for循环无法解决的暴力搜索问题

可以考虑回溯算法，一个在for循环中使用递归嵌套的方法

回溯三部曲

1、递归函数的返回值以及参数

2、回溯函数终止条件

path这个数组的大小如果达到k，说明找到了一个子集大小为k的组合了

3、单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程

for循环每次从startIndex开始遍历，然后用path保存取到的节点i

可以看出backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回

backtracking的下面部分就是回溯的操作了，撤销本次处理的结果

Python代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        path = []
        self.backtracking(n, k, 1, path, res)
        return res
    def backtracking(self, n, k, startIndex, path, res):
        if len(path) == k:
			# 对于此处添加path副本的理解
            res.append(path[:])
            return
        for i in range(startIndex, n+1):
            path.append(i)
            self.backtracking(n, k, i+1, path, res)
            path.pop()

ps：为什么要添加副本呢？

在回溯算法中，path 列表是一个可变对象，而且在递归过程中会不断地被修改（元素的添加和删除）。如果直接将 path 添加到 res 中，那么后续对 path 的修改也会反映在 res 中，因为 res 中存储的是对 path 对象的引用

为了避免这种情况，使用 path[:] 来创建 path 的副本，这样就可以确保 res 中存储的是 path 的快照，不会随着后续对 path 的修改而改变

继续优化可以考虑剪枝

n是给定的所有数，k是组合的大小，len(path)是当前存储的元素的个数

当前位置i之后所剩余的元素个数加上i自己n-i+1再+len(path) >= k，才能保证还有搜的必要

不然直接可以剪去

所以for循环处的条件改写如下：

1
2
3
4
5
# range是左闭右开，所以还得+1
for i in range(startIndex, n-k+len(path)+2):
    path.append(i)
    self.backtracking(n, k, i+1, path, res)
    path.pop()

Leetcode216 组合总和Ⅲ

总体思路跟上一题是一样的

Python代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        path = []
        self.backtracking(k, n, 1, path, res)
        return res
    def backtracking(self, k, n, startIndex, path, res):
        if len(path) == k:
            if sum(path) == n:
                res.append(path[:])
            return
        for i in range(startIndex, 10):
            path.append(i)
            self.backtracking(k, n, i+1, path, res)
            path.pop()

剪枝操作

因为集合从1开始往后找，在遍历的时候，sum肯定是越来越大的

因此，当sum>n时，已经没有必要往下再搜索了

1
2
3
4
5
6
if len(path) == k:
    if sum(path) > n:
        return
    if sum(path) == n:
        res.append(path[:])
    return

1~9是给定的所有数，k是组合的大小，len(path)是当前存储的元素的个数

当前位置i之后所剩余的元素个数加上i自己9-i+1再+len(path) >= k，才能保证还有搜的必要

1
2
3
4
5
# range是左闭右开，所以还得+1
for i in range(startIndex, 9+len(path)-k+2):
    path.append(i)
    self.backtracking(k, n, i+1, path, res)
    path.pop()

Leetcode17 电话号码的字母组合

首先想到for循环暴力解决，但是当digits中数字变多时，for循环就解决不了了

因此考虑回溯

回溯时想不出代码该怎样组织，可以考虑先画出树形结构

很容易得知树的深度(递归部分)，与digits中数字的个数相关

树的宽度(for循环部分)，与数字对应的字母个数有关

接着还是回溯三部曲

1、确定回溯函数参数

首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组res保存起来，放在全局变量里

再来看参数，参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index

这个index不是之前两道题中的``startIndex`

这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度

2、确定终止条件

例如输入用例"23"，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集

那么终止条件就是如果index等于 输入的数字个数len(digits)了（本来index就是用来遍历digits的）

3、确定单层遍历逻辑

首先要取index指向的数字，并找到对应的字符集

然后for循环来处理这个字符集

这个for循环与前两道题也不一样，前两道题是在一个集合里找子集，所以为了不重复需要有startIndex

这题是不同的集合，所以从0开始

Python代码如下

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
class Solution:
    def __init__(self):
        self.letter_map = [
            '',
            '',
            'abc',
            'def',
            'ghi',
            'jkl',
            'mno',
            'pqrs',
            'tuv',
            'wxyz'
        ]
        self.res = []
        self.s = ''
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        self.backtracking(digits, 0)
        return self.res
    def backtracking(self, digits, index):
        if index == len(digits):
            self.res.append(self.s)
            return
        for char in self.letter_map[int(digits[index])]:
            self.s += char
            self.backtracking(digits, index+1)
            self.s = self.s[:-1]

Leetcode39 组合总和

还是差不多的思路

剪枝优化可以考虑先给candidates排个序

Python代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def __init__(self):
        self.res = []
        self.path = []
    def backtracking(self, candidates, target):
        if sum(self.path) == target:
            self.res.append(self.path[:])
            return
        if sum(self.path) > target:
            return
        for i in range(len(candidates)):
            self.path.append(candidates[i])
            self.backtracking(candidates[i:], target)
            self.path.pop()
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.backtracking(candidates, target)
        return self.res

Leetcode40 组合总和Ⅱ

思路大体还是一致的

但这道题跟以前不一样，现在元素有重复值了，需要特别考虑去重的问题

在递归的时候，由于是往后继续找元素，因此不用考虑重复的问题

主要是在for循环进来的时候，假设candidates是排序过的

比如有candidates—> [1,1,1,2,2……]

第一次循环时，1开头之后的所有情况以及遍历过了

下一次循环再到1时，可以跳过了，不然就会有重复集合

添加一个used数组记录元素的是否访问

在回溯时，candidates[i] == candidates[i-1] 但used[i-1] = 1

for循环时，前一个元素已经回溯结束，used对应元素已经回退为0了，因此当candidates[i] == candidates[i-1] and used[i-1] == 0时，说明是新的for循环中，因此在重复的情况下需要continue跳过

Python代码如下

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:
    def __init__(self):
        self.res = []
        self.path = []
    def backtracking(self, candidates, target, startIndex, used):
        if sum(self.path) == target:
            self.res.append(self.path[:])
            return
        if sum(self.path) > target:
            return
        for i in range(startIndex, len(candidates)):
            if i > 0 and candidates[i] == candidates[i-1] and used[i-1] == 0:
                continue
            self.path.append(candidates[i])
            used[i] = 1
            self.backtracking(candidates, target, i+1, used)
            self.path.pop()
            used[i] = 0
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        used = [0] * len(candidates)
        candidates.sort()
        self.backtracking(candidates, target, 0, used)
        return self.res