https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
from typing import List
class Solution(object):
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
def backtrack(first=0):
# 所有数都填完了
if first == n:
res.append(nums[:])
for i in range(first, n):
# 动态维护数组
nums[first], nums[i] = nums[i], nums[first]
# 继续递归填下一个数
backtrack(first + 1)
# 撤销操作
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
res = [] #结果
backtrack()
return res
print(Solution().permute([1,2,3,4]))
print(Solution().permute([1,2,3,4]).__len__())
另一个写法
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
nums.sort()
self.res = []
check = [0 for _ in range(len(nums))] # 全0 推导式
self.backtrack([], nums, check)
return self.res
def backtrack(self, sol, nums, check):
if len(sol) == len(nums): #结束条件 当前结果的长度==列表的长度
self.res.append(sol)
return
for i in range(len(nums)):
if check[i] == 1: # 剪枝条件
continue
check[i] = 1
self.backtrack(sol + [nums[i]], nums, check)
check[i] = 0
https://leetcode-cn.com/problems/permutations-ii/solution/
from typing import List
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
self.res = []
check = [0 for _ in range(len(nums))] # 全0 推导式
self.backtrack([], nums, check)
return self.res
def backtrack(self, sol, nums, check):
if len(sol) == len(nums): # 结束条件 当前结果的长度==列表的长度
self.res.append(sol)
return
for i in range(len(nums)):
if check[i] == 1: # 剪枝条件
continue
if i > 0 and nums[i] == nums[i - 1] and check[i - 1] == 0: # 剪枝条件
continue
check[i] = 1
self.backtrack(sol + [nums[i]], nums, check)
check[i] = 0
print(Solution().permuteUnique([0, 1, 2]))
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
temp = []
def recursion(idx, res):
if idx >= len(candidates) or res >= target:
if res == target:
ans.append(temp[:])
return
temp.append(candidates[idx])
recursion(idx, res + candidates[idx])
temp.pop()
recursion(idx + 1, res)
recursion(0, 0)
return ans
https://leetcode-cn.com/problems/combination-sum/comments/
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(pos: int, rest: int):
nonlocal sequence
if rest == 0:
ans.append(sequence[:])
return
if pos == len(freq) or rest < freq[pos][0]:
return
dfs(pos + 1, rest)
most = min(rest // freq[pos][0], freq[pos][1])
for i in range(1, most + 1):
sequence.append(freq[pos][0])
dfs(pos + 1, rest - i * freq[pos][0])
sequence = sequence[:-most]
freq = sorted(collections.Counter(candidates).items())
ans = list()
sequence = list()
dfs(0, target)
return ans
https://leetcode-cn.com/problems/subsets/
https://leetcode-cn.com/problems/subsets-ii/
文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890
Python Free
邮箱:417803890@qq.com
QQ:417803890
皖ICP备19001818号
© 2019 copyright www.pythonf.cn - All rights reserved
微信扫一扫关注公众号:
Python Free