題目出處

難度

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，可以嘗試直接閱讀程式碼理解

算法說明

此題的前一題為無重複版本，這題要多處理重複，可參考：

https://wongwongnotes-github-io.pages.dev/python/python_leetcode/leetcode-python-78/

經典 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

子集 II · Subsets II