|
目录
一、排列问题
46.?全排列（middle）
47.?全排列 II（middle）
剑指 Offer 38.?字符串的排列（middle）
784.?字母大小写全排列（middle）
二、组合问题
17. 电话号码的字母组合（middle）
39. 组合总和?（middle）(candidates 中的数字可以无限制重复被选取)
40. 组合总和 II?（middle）(candidates 中的每个数字在每个组合中只能使用一次)
77.组合（middle）
216. 组合总和 III?（middle）（与上面的题目区别是：给了res的长度限制，所以这个数字不行，就要腾出位置来给其他的元素）?
三、子集问题
78.子集（middle）
90.子集2（middle）
四、分割问题
93.复原IP地址（middle）
131.分割回文串（middle）
五、棋盘问题
37.解数独（hard）
51.N皇后（hard）
六、其他
491.递增子序列（middle）
332.重新安排行程（middle）
一、排列问题
给定一个不含重复数字的数组?nums?，返回其?所有可能的全排列?。你可以?按任意顺序?返回答案
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
https://leetcode-cn.com/problems/permutations/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-hui-s-mfrp/
这里和77.组合问题、131.切割问题和78.子集问题最大的不同就是for循环里不用startIndex了。
因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。
而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
"""
middle
dfs 回溯法
"""
class Solution(object):
def __init__(self):
self.res = []
self.path = []
def permute(self, nums):
self.dfs(nums)
return self.res
def dfs(self, nums):
if len(self.path) == len(nums):
self.res.append(self.path[:]) # 此时说明找到了一组
for i in range(len(nums)):
if nums[i] in self.path: # path里已经收录的元素，直接跳过
continue
self.path.append(nums[i])
self.dfs(nums) # 递归
self.path.pop() # 回溯
总结
- 每层都是从0开始搜索而不是startIndex
- 需要used数组记录path里都放了哪些元素了
给定一个可包含重复数字的序列?nums?，按任意顺序?返回所有不重复的全排列。
输入：nums = [1,1,2]
输出：[[1,1,2], [1,2,1], [2,1,1]]
class Solution:
def permuteUnique(self, nums):
result = []
self.dfs(nums,0,[],result)
print(list(result))
def dfs(self,nums,start,path,result):
if len(path)==len(nums):
if path not in result:
result.append(path[:])
return
for i in range(start,len(nums)):
path.append(nums[i])
self.dfs(nums,i+1,path,result)
# path.pop()
输入一个字符串，打印出该字符串中字符的所有排列。里面不能有重复元素。
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
class Solution:
def permutation(self, s: str) -> List[str]:
res = []
if not s:return res
self.dfs("", res, s)
return list(set(res))
def dfs(self, path, res, s):
# 定义dfs出口
if s=='':res.append(path)
# 轮流当首字母
for i in range(len(s)):
self.dfs(path+s[i], res, s[:i]+s[i+1:])
return res
给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
示例：
输入：S = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]
二、组合问题
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
输入：digits = "2"
输出：["a","b","c"]
# 求abc和def的全排列
# 全排列就是回溯, 求最短路径也是DFS
# DFS
class Solution(object):
def letterCombinations(self, digits):
# 存储结果的数组
res = []
inputstr = []
if len(digits) == 0:
return res
hash_map = {0:"",1:"",2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"}
for i in digits:
inputstr.append(hash_map[int(i)])
# print(inputstr) # ['abc', 'def']
# 闭包
def dfs(cur_str,i,res):
if len(cur_str)==len(inputstr): # abc def ghi
res.append(cur_str)
return
for count in range(len(inputstr[i])): # abc
dfs(cur_str+inputstr[i][count],i+1,res)
dfs("",0,res)
return res
39. 组合总和?（middle）(candidates 中的数字可以无限制重复被选取)
给定一个无重复元素的正整数数组?candidates?和一个正整数?target?，找出?candidates?中所有可以使数字和为目标数?target?的唯一组合。
candidates?中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。?
输入: candidates = [2,3,6,7],
target = 7
输出: [[7],[2,2,3]]
# 给定一个无重复元素的数组 candidates 和一个目标数 target ，
# 找出 candidates 中所有可以使数字和为 target 的组合。
# candidates 中的数字可以无限制重复被选取。
class Solution:
def combinationSum(self, candidates, target):
result = []
item = []
candidates.sort() # 首先要排序，必不可少，记得归纳总结这里，什么时候要排序？？
self.dfs(candidates,target,0,item,result)
return result
def dfs(self,candidates,target,start,item,result):
if target==0:
# print(item)
result.append(item[:])
return
for i in range(start,len(candidates)):
# 剪枝
if candidates[i]>target:
return
self.dfs(candidates,target-candidates[i],i,item+[candidates[i]],result)
40. 组合总和 II?（middle）(candidates 中的每个数字在每个组合中只能使用一次)
# 与上一道题唯一的区别就在于下面这个递归我们加了1，这样下次递归的循环就从i+1开始了。
给定一个数组?candidates?和一个目标数?target?，找出?candidates?中所有可以使数字和为?target?的组合。
candidates?中的每个数字在每个组合中只能使用一次。
输入: candidates =?[2,5,2,1,2], target =?5,
输出:
[
[1,2,2],
[5]
]
# 给定一个数组 candidates 和一个目标数 target ，
# 找出 candidates 中所有可以使数字和为 target 的组合。
# candidates 中的每个数字在每个组合中只能使用一次。
# -----------------------------------------------
# 递归的时候将 idx 加 1（需判断是否超出candidates的范围），另外由于题目输入的candidates可能包含相同的元素，
# 所以我们需要对得到的答案进行去重处理。
class Solution:
def combinationSum2(self, candidates, target):
path=[]
result=[]
candidates.sort()
self.dfs(candidates,target,0,path,result)
return result
# 我的想法是每次找过的元素都标记一下，然后下次找的时候就不可以选这个了
# i+1表明一个数字只能使用一次
def dfs(self,candidates,target,start,path,result):
# 判断出口
if target == 0 and path not in result:
result.append(path[:])
return
# 开始循环遍历
for i in range(start,len(candidates)):
if candidates[i]>target:
return
# i+1表明一个数字只能使用一次，这样下次递归的循环就从i+1开始了
self.dfs(candidates,target-candidates[i],i+1,path+[candidates[i]],result)
给定两个整数?n?和?k，返回范围?[1, n]?中所有可能的?k?个数的组合。
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
77.组合（剪剪枝）
216. 组合总和 III?（middle）（与上面的题目区别是：给了res的长度限制，所以这个数字不行，就要腾出位置来给其他的元素）?
216：[[1, 2, 6], [1, 3, 5], [2, 3, 4]]；40：[[1, 2, 2], [5]] （个人理解，求指点啊~~）
找出所有相加之和为?n 的?k?个数的组合。组合中只允许含有 1 -?9 的正整数，并且每种组合中不存在重复的数字。
说明：1、所有数字都是正整数。2、解集不能包含重复的组合。?
输入: k = 3, n = 7
输出: [[1,2,4]]
# 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
# 说明：
# 所有数字都是正整数。
# 解集不能包含重复的组合。
class Solution:
def combinationSum3(self, k, n):
path=[]
result=[]
nums = [i for i in range(1,10)]
self.dfs(nums,k,n,0,path,result)
return result
def dfs(self,nums,k,n,start,path,result):
if k==0 and n==0 and path not in result:
result.append(path[:])
return
for i in range(start,len(nums)):
if nums[i]>n or k<0:
return
k-=1
self.dfs(nums,k,n-nums[i],i+1,path+[nums[i]],result)
k+=1
# 控制path
class Solution:
def combinationSum3(self, k, n):
path=[]
result=[]
nums = [i for i in range(1,10)]
self.dfs(nums,k,n,0,path,result)
return result
def dfs(self,nums,k,n,start,path,result):
if len(path)==k and n==0 and path not in result:
result.append(path[:])
return
for i in range(start,len(nums)):
if nums[i]>n or k<0:
return
# k-=1
path.append(nums[i])
self.dfs(nums,k,n-nums[i],i+1,path,result)
# k+=1
path.pop()
三、子集问题
给你一个整数数组?nums?，数组中的元素?互不相同?。返回该数组所有可能的子集（幂集）。
解集?不能?包含重复的子集。你可以按?任意顺序?返回解集。
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
?
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
# 输入: [1,2,2] 输出:[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
class Solution(object):
def subsetsWithDup(self, nums):
path = []
result = []
nums.sort()
self.dfs(nums,0,path,result)
return result
def dfs(self,nums,start,path,result):
if path not in result:
result.append(path[:])
if start == len(nums): # 之前报错，改了这里
return
for i in range(start,len(nums)):
path.append(nums[i])
self.dfs(nums,i+1,path,result)
path.pop()
四、分割问题
五、棋盘问题
六、其他
回溯算法总结篇
|