題目出處
難度
Medium
個人範例程式碼
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
if not nums:
return [[]]
nums.sort()
ans = []
self.dfs(nums, 0, [], ans)
return ans
def dfs(self, nums, start, combination, ans):
ans.append(combination[:]) # deepcopy
# end of recursion, define ans split
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: # only take first duplicate
continue
combination.append(nums[i])
self.dfs(nums, i+1, combination, ans)
combination.pop()
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
算法說明
- 此題的前一題為無重複版本,這題要多處理重複,可參考:
經典 DFS 的組合問題, 這題要多處理重複的部分,
我們先 sort() 確保有一致的順序,
我們利用 i > start 來確保跟開始項目相同時,第一組重複有被計算到
注意:不是 i > 0,而是 i > start
start 位置就是代表重複字母的第一個字,除了第一次判斷會拿之外,後面都不會再拿。
if i > start and nums[i] == nums[i-1]: # only take first duplicate
continue
input handling
如果沒有 nums,return [[]]
Boundary conditions
用 dfs 內的 for loop 控制搜尋範圍
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python | ||
210 | Course Schedule II | BFS (拓樸) | Graph | Python | ||
[Lint] 892 | Alien Dictionary |