491. Non-decreasing Subsequences
- 思路
- example
- 返回所有該數(shù)組中不同的遞增子序列(至少2個(gè)元素): 暴力回溯/DFS
- 有重復(fù)元素
- 去重: 同層 (橫向遍歷）
- 不能排序
- 利用hash (dict, set, list等）同層去重, key = 數(shù)值
- 終止條件：start == len(nums), 縱向
- 遞增子序列中 至少有兩個(gè)元素
有重不可復(fù)選
if len(path) >= 2:
res.append(path[:])
- 桶裝球 （球=數(shù)字）
- 桶：縱向遍歷
- 球：橫向遍歷
- 復(fù)雜度. 時(shí)間：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 中的所有整數(shù) 互不相同
- 不需要去重
- 使用used數(shù)組避免重復(fù)取元素
- used[index] = True or False
-
start = 0
無重不可復(fù)選
- 桶裝球 （球=數(shù)字）
- 復(fù)雜度. 時(shí)間：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
- 可包含重復(fù)數(shù)字
-
去重 （同層去重，樹層去重）
- 排序
- 第一個(gè)條件：used[i] = True: 第i個(gè)元素已經(jīng)在前面幾層使用過，當(dāng)前層不能再取。
- i > 0 and nums[i] == nums[i-1]: 重復(fù)元素。此時(shí)如果 used[i-1] == False，說明該數(shù)字(nums[i]=nums[i-1])在同層已經(jīng)遍歷過，不需要再取第i個(gè)數(shù)字接著遍歷了。
-
注意當(dāng)i > 0 and nums[i] == nums[i-1] and used[i-1] == True時(shí)，第i個(gè)元素nums[i]是可以取的 （nums[i-1]在前面幾層取得，不沖突）。例子：[1,1,2]
-
-
去重 （同層去重，樹層去重）
- 桶裝球 （球=數(shù)字）
- 桶：縱向遍歷，深度
- 球：橫向遍歷 ，寬度（可選范圍，去重）
- 復(fù)雜度. 時(shí)間：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 # 樹層避免重復(fù)取，同層去重
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
