491.递增子序列
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = []
self.tracebacking(nums, 0, [], res)
return res
def tracebacking(self, nums, start, path, res):
if len(path) >= 2:
res.append(path[:])
uset = set() # 用于本层去重
for i in range(start, len(nums)):
if nums[i] in uset or (path and path[-1] > nums[i]): # 同一层的相同元素，
continue
uset.add(nums[i])
path.append(nums[i])
self.tracebacking(nums, i+1, path, res)
path.pop()
46.全排列
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
used = [False]*len(nums)
self.tracebacking(nums, used, [], res)
return res
def tracebacking(self, nums, used, path, res):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
path.append(nums[i])
used[i] = True
self.tracebacking(nums, used, path, res)
path.pop()
used[i] = False
47.全排列 II
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
used = [False]*len(nums)
self.tracebacking(nums, used, [], res)
return res
def tracebacking(self, nums, used, path, res):
if len(path) == len(nums):
res.append(path[:])
for i in range(len(nums)):
if (i > 0 and nums[i] == nums[i-1] and not used[i-1]) or used[i]:
continue
path.append(nums[i])
used[i] = True
self.tracebacking(nums, used, path, res)
path.pop()
used[i] = False