[LeetCode] 90. Subsets II

轉自LeetCode

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

<Solution>

這題是 Subset 的衍生題，這次會有重複的數字出現，但最後的答案不能有重複的 subset

根據之前 DFS 的基礎，配合 set 來濾掉重複的 subset

以及因為要讓 set 能濾掉重複的 subset，在進行 DFS 之前，先對 nums 進行一次 sort

code 如下
c++

Kotlin

還有一種 iterative 的解法(參考資料)

想法如下

• 如果沒有重複數字，則每個數字就是要或不要兩種選擇。空集合代表的就是不要的選項，而要這個選項，就是把當前的數字放到之前所有的 subsets 中，形成新的 subsets

• 如果有重複數字，舉例有三個6，那麼會有 (3 + 1) 種狀況

• 全部都不放，也就是空集合的這個 subset

• 只放一個

• 只放兩個

• 全部放

所以，在放置數字來找到 subset 之前，先知道當前的數字有重覆幾次

這樣就可以用上面的邏輯，來找到所有 subsets

而為了能算出數字有重覆幾次，必須先對 nums 做一次 sort

code如下

C++

Java