491. Non-decreasing Subsequences
- 思路
- example
- 返回所有该数组中不同的递增子序列(至少2个元素): 暴力回溯/DFS
- 有重复元素
- 去重: 同层 (横向遍历）
- 不能排序
- 利用hash (dict, set, list等）同层去重, key = 数值
- 终止条件：start == len(nums), 纵向
- 递增子序列中 至少有两个元素
有重不可复选
if len(path) >= 2:
res.append(path[:])
- 桶装球 （球=数字）
- 桶：纵向遍历
- 球：横向遍历
- 复杂度. 时间：O(), 空间: O()
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
def backtrack(nums, start):
if len(path) >= 2:
res.append(path[:])
if start == len(nums): # 可不需要
return
used = set()
for i in range(start, len(nums)):
if nums[i] in used or (path and nums[i] < path[-1]): # 递增子序列
continue
path.append(nums[i])
backtrack(nums, i+1)
path.pop()
used.add(nums[i])
res, path = [], []
backtrack(nums, 0)
return res
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
def backtrack(start):
if len(path) >= 2:
res.append(path[:])
used = set()
for i in range(start, n):
if nums[i] in used:
continue
if path == [] or nums[i] >= path[-1]:
path.append(nums[i])
backtrack(i+1)
path.pop()
used.add(nums[i])
res, path = [], []
n = len(nums)
backtrack(0)
return res
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
def backtrack(start_idx):
if len(path) >= 2:
res.append(path[:])
if start_idx == len(nums):
return
used = set()
for i in range(start_idx, len(nums)):
if nums[i] in used:
continue
if path and nums[i] < path[-1]:
continue
path.append(nums[i])
backtrack(i+1)
path.pop()
used.add(nums[i]) # !!!
res, path = [], []
backtrack(0)
return res
46. 全排列
- 思路
- example
- 返回其所有可能的全排列: 暴力回溯
- nums 中的所有整数 互不相同
- 不需要去重
- 使用used数组避免重复取元素
- used[index] = True or False
-
start = 0
无重不可复选
- 桶装球 （球=数字）
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(nums, path):
if len(path) == len(nums):
res.append(path[:])
for i in range(len(nums)):
if used[i] == True:
continue
path.append(nums[i])
used[i] = True
backtrack(nums, path)
used[i] = False
path.pop()
res, path = [], []
used = [False for _ in range(len(nums))]
backtrack(nums, path)
return res
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(depth):
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
backtrack(depth+1)
used[i] = False
path.pop()
res, path = [], []
used = [False for _ in range(len(nums))]
backtrack(1)
return res
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(used):
if len(path) == n:
res.append(path[:])
return
for i in range(n):
if used[i]:
continue
path.append(nums[i])
used[i] = True
backtrack(used)
used[i] = False
path.pop()
n = len(nums)
used = [False for _ in range(n)]
res, path = [], []
backtrack(used)
return res
47. 全排列 II
- 思路
- example
- 可包含重复数字
-
去重 （同层去重，树层去重）
- 排序
- 第一个条件：used[i] = True: 第i个元素已经在前面几层使用过，当前层不能再取。
- i > 0 and nums[i] == nums[i-1]: 重复元素。此时如果 used[i-1] == False，说明该数字(nums[i]=nums[i-1])在同层已经遍历过，不需要再取第i个数字接着遍历了。
-
注意当i > 0 and nums[i] == nums[i-1] and used[i-1] == True时，第i个元素nums[i]是可以取的 （nums[i-1]在前面几层取得，不冲突）。例子：[1,1,2]
-
-
去重 （同层去重，树层去重）
- 桶装球 （球=数字）
- 桶：纵向遍历，深度
- 球：横向遍历 ，宽度（可选范围，去重）
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def backtrack(nums, path):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i] == True or (i > 0 and nums[i] == nums[i-1] and used[i-1] == False):
continue # 树层避免重复取，同层去重
path.append(nums[i])
used[i] = True
backtrack(nums, path)
used[i] = False
path.pop()
res, path = [], []
nums.sort()
used = [False for _ in range(len(nums))]
backtrack(nums, path)
return res
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def backtrack(depth):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1] and used[i-1] == False:
continue
if used[i] == True:
continue
path.append(nums[i])
used[i] = True
backtrack(depth+1)
used[i] = False
path.pop()
res, path = [], []
nums.sort()
used = [False for _ in range(len(nums))]
backtrack(1)
return res
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def backtrack(used):
if len(path) == n:
res.append(path[:])
return
for i in range(n):
if used[i]:
continue
if i > 0 and used[i-1] == False and nums[i] == nums[i-1]: # !!!
continue
path.append(nums[i])
used[i] = True
backtrack(used)
used[i] = False
path.pop()
n = len(nums)
nums.sort()
used = [False for _ in range(n)]
res, path = [], []
backtrack(used)
return res
- 拓展，下面代码做的是树枝去重，亦可。
if used[i] or (i > 0 and nums[i] == nums[i-1] and used[i-1] == True):
continue
