代码随想录算法训练营 Day 19
Published:
回溯算法
几大适用问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
Q1. LeetCode 77
了解回溯算法的基础框架
解法1
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
def backtracking(n, k, start, path):
# 终止条件，注意return
if len(path) == k:
res.append(path[:])
return
# 遍历集合元素
for i in range(start, n + 1):
# 处理当前元素
path.append(i)
# 调用递归函数
backtracking(n, k, i + 1, path)
# 回溯操作，删去加入元素
path.pop()
backtracking(n, k, 1, [])
return res
解法2: 剪枝优化
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
def backtracking(n, k, start, path):
# 终止条件，注意return
if len(path) == k:
res.append(path[:])
return
# 遍历集合元素。注意停止位置，比如当n=4，k=2时，不需要考虑4作为第一个元素的情况
for i in range(start, n + 2 - (k - len(path))):
# 处理当前元素
path.append(i)
# 调用递归函数
backtracking(n, k, i + 1, path)
# 回溯操作，删去加入元素
path.pop()
backtracking(n, k, 1, [])
return res
复杂度分析
时间复杂度：O($n \times 2^n$) 空间复杂度：O($n$)
Q2. LeetCode 216
剪枝的多种情况：1. 考虑元素个数；2. 考虑当前和与目标值的大小
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
def backtracking(k, target, start, arr, s):
if s > target:
return
if len(arr) == k:
if s == target:
res.append(arr[:])
return
for i in range(start, 11 - (k - len(arr))):
arr.append(i)
s += i
backtracking(k, target, i + 1, arr, s)
s -= i
arr.pop()
backtracking(k, n, 1, [], 0)
return res
复杂度分析
时间复杂度：O($n \times 2^n$) 空间复杂度：O($n$)
Q3. LeetCode 17
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
num_to_letter = [
'',
'',
'abc',
'def',
'ghi',
'jkl',
'mno',
'pqrs',
'tuv',
'wxyz'
]
res = []
if not digits:
return res
def backtracking(idx, letters):
if idx == len(digits):
res.append(''.join(letters))
return
d = int(digits[idx])
for l in num_to_letter[d]:
letters.append(l)
backtracking(idx + 1, letters)
letters.pop()
backtracking(0, [])
return res
复杂度分析
时间复杂度：O($3^m \times 4^n$) 空间复杂度：O($3^m \times 4^n$) m,n分别为对应三个字母和四个字母的数字个数