😡😡😡
声明：
算法基于https://labuladong.github.io/
python语言实现
core mind
46.permutations
47.permutations-ii
51.n-queens
77.combinations
78.subsets
90.subsets-ii
698.partition-to-k-equal-sum-subsets
😡😡😡
core mind
【回溯算法秒杀所有排列/组合/子集问题】https://labuladong.github.io/algo/4/29/107/
"""
【回溯问题】<=>【决策树遍历】<=>【纯暴力穷举】<=>【无重复子问题的递归】：4 key point[choose list + choose + track + end state]
解决一个回溯问题，实际上就是一个决策树的遍历过程。
站在回溯树的一个节点上，你只需要思考 3 个问题：
1、【选择列表】：也就是你当前可以做的选择 => 对应题目中给出的输入列表
2、【选择】：选择列表指针i，用于遍历选择列表，作出选择 ，递归过程：
def backtrack(i:int[输入列表指针], track:List[存储符合题意的选择，即路径列表])
for i in range(len(input_list)):
# 2.1 递归出口：选择列表指针i移动至表尾，所有元素均得到处理后，使用return语句返回
if i==len(input_list):
1.if [satisfy answer]:return True
2.or res.append(track[.copy()])
# 2.2 核心递归部分：选择列表指针i逐步移动至表尾
=> 不符合题意的选择：if [choose unsatisfied]: continue
continue语句跳过该选择，进入下一次循环
=> 符合题意的选择：if [choose satisfied]:
a 选择列表--移除--该选择: input_list.remove(input_list[i])
b 路径列表--加入--该选择: track.append(input_list[i])
[if] backtrack(i+1, track) [return] # 将选择列表指针i后移这一动作打入递归调用过程
=> 递归调用后撤销【符合题意的选择】，【还原决策树】
a 选择列表--加入--该选择: input_list.append(input_list[i])
b 路径列表--移除--该选择: track.remove(input_list[i])
3、【路径】：存储于已经做出的、符合题意的选择。
4、【结束条件】：也就是到达决策树底层，无法再做选择的条件。
"""
# 核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」
'''
class Solution:
def outer_func(self, nums: List[int]) -> [return_type]:
# 记录结果集：存储各个路径列表track
result = []
# 记录符合题意的选择列表指针i对应的值nums[i]
track = []
# 仅限排列使用：标记数组used，用于记录nums[i]是否被使用
used = [False for i in range(len(nums))]
组合|子集：def backtrack(选择列表指针i, 存储符合题意的选择nums[i]路径列表track):
排列：def backtrack(存储符合题意的选择nums[i]路径列表track, 标记数组used):
if 满足结束条件:
result.add(track)
return
for 选择列表指针i in range(len(选择列表nums)):
1. 选择判断：不符合 or 符合 题意
1.1 针对不符合题意的选择：
if [choose unsatisfied]: continue
continue语句跳过该选择，进入下一次循环
1.2 针对符合题意的选择：记录在存储【符合题意的选择列表指针i对应的值】的 【路径列表track】中
将该选择从选择列表移除:used[i]=True
路径.add(选择)：track.append(nums[i])
2.递归调用：
组合|子集：backtrack(选择列表指针i后移一位i+1, 路径列表track)
# 通过保证元素之间的相对顺序不变【即在递归调用过程中使 列表指针变量i+1】来防止出现重复的子集。
排列：backtrack(路径列表track, 记录指针变量i是佛被访问过的used标记数组)
3.撤销选择：（递归后撤销选择，还原该决策树，进行下一次决策树递归过程）将符合题意的选择列表指针值 从 路径列表track中移除
路径列表.remove(选择):track.remove(nums[i])
将该选择再加入选择列表:used[i]=False
'''
😡😡😡
46.permutations
'''
NOTE:LeetCode提示超时时，去掉导包语句及所有注释即可通过
'''
from typing import List
class Solution:
'''
【排列（元素无重不可复选）】
'''
def permute(self, nums: List[int]) -> List[List[int]]:
# 最终结果集result：存储track
res = []
# 符合题意的选择列表指针集：存储符合题意的选择列表指针i对应的值nums[i]
track = []
# 标记数组used，用于记录nums[i]是否被使用
used = [False for j in range(len(nums))]
def backtrack(track: List[int], used: List[bool]):
# 结束条件：当track的长度等于nums的长度时，说明已经完成了一个全排列
if len(track) == len(nums):
# NOTE：此处添加的是track的副本，否则当后续撤销选择时，track指向的内容将不存在，导致res全为空
res.append(track.copy())
return
for i in range(len(nums)):
# 1.1 针对不符合题意的选择i：跳过该选择，进行下一次循环判断
if used[i]: continue
# 1.2 针对符合题意的选择i：加入存储 符合题意的选择 的路径列表tarck ，并将i标记为已经被使用过。
track.append(nums[i])
used[i] = True
# 2. core：recursive
backtrack(track, used)
# 3.递归之后撤销选择，还原该决策树：路径列表中移出nums[i]这一选择，并将i标记为未被使用。
track.remove(nums[i])
used[i] = False
backtrack(track, used)
return res
def main():
# Input: nums = [1,2,3]
# Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
solution1 = Solution()
print(solution1.permute(nums=[1, 2, 3]))
# Input: nums = [0,1]
# Output: [[0,1],[1,0]]
solution2 = Solution()
print(solution2.permute(nums=[0, 1]))
# Input: nums = [1]
# Output: [[1]]
solution3 = Solution()
print(solution3.permute(nums=[1]))
if __name__ == '__main__':
main()
😡😡😡
47.permutations-ii
'''
solution3:存在问题，带解决
'''
from typing import List
class Solution:
'''
【排列（元素可重不可复选）】
'''
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
track = []
used = [False for i in range(len(nums))]
# nums.sort()
def backtrack(nums: List[int]):
# 递归出口
if len(track) == len(nums):
res.append(track.copy())
return
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1] and nums[i - 1] is False:
continue
if used[i] == True:
continue
elif used[i] == False:
track.append(nums[i])
used[i] = True
backtrack(nums)
track.remove(nums[i])
used[i] = False
backtrack(nums)
# res_sorted = [sorted(i) for i in res]
res_nodup_tuple = list(set([tuple(i) for i in res]))
res_nodup_list = [list(i) for i in res_nodup_tuple]
return res_nodup_list
def main():
# Input: nums = [1,1,2]
# Output:
# [[1,1,2],
# [1,2,1],
# [2,1,1]]
solution1 = Solution()
print(solution1.permuteUnique(nums=[1, 1, 2]))
# Input: nums = [1,2,3]
# Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
solution2 = Solution()
print(solution2.permuteUnique(nums=[1, 2, 3]))
# Input:
# [2,2,1,1]
# Output:
# [[1,2,1,2],[1,2,2,1],[2,2,1,1],[2,1,1,2],[1,1,2,2]]
# Expected:
# [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]
solution3 = Solution()
print(solution3.permuteUnique([2, 2, 1, 1]))
if __name__ == '__main__':
main()
😡😡😡
51.n-queens
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
# 最终结果集result：存储board
res = []
# 符合题意的选择列表指针集：存储符合题意的选择列表指针row 对应的值
# board存储的数据结构[".Q..","...Q","Q...","..Q."]
board = [['.'] * n for i in range(n)]
def isValid(board: List, row: int, column: int) -> bool:
# 1.该格所在的整列不能有Q
for i in range(n):
if board[i][column] == 'Q':
return False
# 2.该格左上连线不能有Q
i = row - 1
j = column - 1
while i >= 0 and j >= 0: # NOTE:边界条件取值范围，是否带等
if board[i][j] == 'Q':
return False
else:
i -= 1
j -= 1
# 3.该格右上连线不能有Q
i = row - 1
j = column + 1
while i >= 0 and j <= n - 1:
if board[i][j] == 'Q':
return False
else:
i -= 1
j += 1
return True
def backtrack(board: List, row: int):
# 1.回溯出口：找到一个满足条件的board
if row == len(board):
board_str = [''.join(list_i) for list_i in board]
res.append(board_str)
return
for column in range(n):
# 1. 选择判断：不符合 or 符合 题意
# 1.1 针对不符合题意的选择：
if isValid(board, row, column) == False:
continue
# 1.2 针对符合题意的选择：记录在board中
board[row][column] = 'Q'
# 2. 核心递归过程：进入下一层决策树,即在下一行放皇后Q
backtrack(board, row + 1)
# 3.递归后：撤销选择，将针对符合题意的选择从board中移除
board[row][column] = '.'
# 选择列表 行指针row 从0向下一次移动
backtrack(board, 0)
return res
def main():
# Input: n = 4
# Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
# Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
solution1 = Solution()
print(solution1.solveNQueens(n=4))
# Input: n = 1
# Output: [["Q"]]
solution2 = Solution()
print(solution2.solveNQueens(n=1))
if __name__ == '__main__':
main()
😡😡😡
77.combinations
from typing import List
class Solution:
'''
【组合（元素无重不可复选）】
'''
def combine(self, n: int, k: int) -> List[List[int]]:
# 结果集res:List[List[int]],存储各个track
res = []
# 符合题意的选择集
track = []
# 元素顺序保证start
def backtrack(start):
# 递归出口
if len(track) == k:
res.append(track.copy())
return
# NOTE:指针变量i每次从start位开始递归
for i in range(start, n + 1, 1):
track.append(i)
backtrack(i + 1)
track.remove(i)
backtrack(1)
return res
def main():
# Input: n = 4, k = 2
# Output:
# [
# [2,4],
# [3,4],
# [2,3],
# [1,2],
# [1,3],
# [1,4],
# ]
solution1 = Solution()
print(solution1.combine(n=4, k=2))
print('---')
# Input: n = 1, k = 1
# Output: [[1]]
solution2 = Solution()
print(solution2.combine(n=1, k=1))
if __name__ == '__main__':
main()
😡😡😡
78.subsets
from typing import List
class Solution:
'''
【子集（元素无重不可复选）】
'''
# Input: nums = [1,2,3]
# Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
# 子集问题 <==> 组合问题 ：通过保证元素之间的相对顺序不变【即在递归调用过程中使：列表指针变量i+1】来防止出现重复的子集
def subsets(self, nums: List[int]) -> List[List[int]]:
# 结果集res:List[List[int]]，存储各个track
res = []
# 记录各个子集：List[int]
track = []
def backtrack(start: int):
# 0.结果集更新位置
res.append(track.copy())
# 2.注意i的起始位start
# NOTE:以下语句将会时i在0、1之间反复横跳，导致无限递归
# for i in range(len(nums)):
for i in range(start, len(nums), 1):
# 递归前：将选择i的值 加入 路径列表track
track.append(nums[i])
# 递归：通过保证元素之间的相对顺序不变【即在递归调用过程中使：列表指针变量i+1】来防止出现重复的子集
backtrack(i + 1)
# 递归后：将选择i的值 移出于 路径列表track
track.remove(nums[i])
backtrack(0)
return res
def main():
# Input: nums = [1,2,3]
# Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
solution1 = Solution()
print(solution1.subsets(nums=[1, 2, 3]))
print('---')
# Input: nums = [0]
# Output: [[],[0]]
solution2 = Solution()
print(solution2.subsets(nums=[0]))
if __name__ == '__main__':
main()
😡😡😡
90.subsets-ii
from typing import List
class Solution:
'''
【子集|组合（元素可重不可复选）】
需要进行剪枝，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历。
体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过。
'''
# Input: nums = [1,2,2]
# Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
# 按升序排序，使相同元素靠在一起，后续在递归过程中对于相同元素只处理一次，后续相同元素跳过。
nums.sort()
res = []
track = []
def backtrack(start: int):
# update res position
# NOTE:此处添加的是路径列表track的一份拷贝值，否则在后续移除元素过程中致使track为空，最后导致res中什么也没加进去
res.append(track.copy())
for i in range(start, len(nums), 1):
# 只处理一次相同元素，注意移动指针前需进行边界条件限制：
# 指针前移i-1，需先保证 i>start
# 指针后移1+1，需先保证 i
# wrong:
# [[], [1], [1, 2], [1, 2, 2], [1, 2], [2], [2, 2], [2]]
# if nums[i] < len(nums) - 1 and nums[i] == nums[i + 1]:
# continue
# right:
# 剪枝逻辑，值相同的相邻树枝，只遍历第一条
# [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
if i > start and nums[i] == nums[i - 1]:
continue
track.append(nums[i])
backtrack(i + 1)
track.remove(nums[i])
backtrack(0)
return res
def main():
# Input: nums = [1,2,2]
# Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
solution1 = Solution()
print(solution1.subsetsWithDup(nums=[1, 2, 2]))
# Input: nums = [0]
# Output: [[],[0]]
solution2 = Solution()
print(solution2.subsetsWithDup(nums=[0]))
if __name__ == '__main__':
main()
😡😡😡
698.partition-to-k-equal-sum-subsets
'''
NOTE:存在问题，还未解决
38 / 159 test cases passed.
Status: Time Limit Exceeded
'''
from typing import List
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
sum = 0
for p in range(len(nums)): sum += nums[p]
if sum % k != 0 or k > len(nums): return False
target = sum / k
buckets = [0 for p in range(k)]
def backtrack(i: int, buckets: List) -> bool:
# 1.递归出口：指针变量i遍历到len(nums)，
# NOTE:出口条件为决策完最后一个元素[len(nums)-1]，i前移一位后指向len(nums)
if i == len(nums):
for bucket in buckets:
if bucket != target: return False
# 若每个桶的和都=目标值target，则可均分为k等分
return True
# 2.遍历k个桶
for j in range(k):
# 2.1 递归前做选择，两种情况：nums[i] 可 | 不可 放入桶buckets[j]?
if buckets[j] + nums[i] > target:
continue
elif buckets[j] + nums[i] <= target:
buckets[j] += nums[i]
# 2.2 递归：将遍历nums这一过程打入递归
# NOTE:递归部分需要有返回值，否则该递归调用结果没有返回值，递归调用结果被舍弃，默认将None赋给res
if backtrack(i + 1, buckets): return True
# 2.3 递归后撤销选择
buckets[j] -= nums[i]
# NOTE：nums[i]装入哪个桶都不行
return False
return backtrack(0, buckets)
def main():
# Input: nums = [4,3,2,3,5,2,1], k = 4
# Output: true
# Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
solution1 = Solution()
print(solution1.canPartitionKSubsets(nums=[4, 3, 2, 3, 5, 2, 1], k=4))
# Input: nums = [1,2,3,4], k = 3
# Output: false
solution2 = Solution()
print(solution2.canPartitionKSubsets(nums=[1, 2, 3, 4], k=4))
# Input: nums = [730,580,401,659,5524,405,1601,3,383,4391,4485,1024,1175,1100,2299,3908], k = 4
# sum=28668 / 4 = 7167
# Output: false
# solution3 = Solution()
# print(solution3.canPartitionKSubsets(nums=[730,580,401,659,5524,405,1601,3,383,4391,4485,1024,1175,1100,2299,3908], k=4))
if __name__ == '__main__':
main()
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）