這個和第一個子集不同的地方是數組中存在重複元素,仍然使用回溯法。将原始的資料排序,仍然使用第一個子集題的代碼,隻是每次在加入到res數組時判斷數組中是否已經包括了這個子集,但是這種判斷操作比較費時,在leedcode嘗試過。我們使用另外一種判斷方式,就是如果目前的元素和前一個元素是相同的,那麼就跳過,沒有比較計算以目前元素開頭的子集,因為在上一個元素開頭的子集中一定已經包含了這些子集。重點還是要了解回溯法的運作機制,就會一目了然。
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
n = len(nums)
if n > 0:
nums.sort()
def helper(i, tmp):
#if tmp not in res:
res.append(tmp)
for j in range(i, n):
if j > i and nums[j] == nums[j - 1]:
continue
helper(j + 1, tmp + [nums[j]])
helper(0, [])
return res