算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問題叫做?子集 II，我們先來看題面：

https://leetcode-cn.com/problems/subsets-ii/

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

題意

給定一個可能包含重復元素的整數數組 nums，返回該數組所有可能的子集(冪集)。說明：解集不能包含重復的子集。樣例

輸入: [1,2,2]
輸出:[
??[2],[1],[1,2,2],[2,2],[1,2],[]
]

解題

https://www.cnblogs.com/techflow/p/13489811.html

題解

全排列的問題也好，獲取子集也好，這些問題都已經算是老生常談了，我們之前做過不少。這些問題經過轉化之后，本質上還是搜索問題。我們在樣本空間當中搜索所有合法的解，存儲起來。這道題的前身LeetCode78題用的正解也是搜索的解法，對于使用搜索算法來解這道題問題不大，但問題是針對數組當中的重復元素我們應該怎么樣來處理。最簡單也是最容易想到的方法當然是先把所有的子集全部找到之后，我們再進行去重。如果采用這樣的方法，還有一個便利是我們可以不用遞歸，而是可以通過二進制枚舉的方法獲取所有的子集。但也有一個問題，問題就是復雜度。我們把集合當中的每一個數字都看成是獨立的，那么對于每一個數字來說都有取和不取兩種方案。對于n個數字來說，方案總數當然就是。并且我們還需要對這個集合進行去重，這帶來的開銷可想而知。當然針對這個問題我們也有解決方案比如可以用hash算法將一個集合hash成一個數，如果hash值一樣說明集合的構成相同。這樣我們就可以通過對數字去重來實現集合去重了。但這樣仍然不是完美的，首先hash算法也不是百分百可靠的，也可能會出現hash值碰撞的情況。其次，這種方案的實現復雜度也很大，我們找出所有集合之后再通過hash算法進行過濾，整個過程非常麻煩。很明顯，這題一定還存在更好的方法。既然事后找補不靠譜，那么我們可以試著事前避免。也就是說我們在搜索所有子集的時候就設計一種機制可以過濾掉重復的集合或者是保證重復的集合不會出現。我們可以分析一下重復的集合出現的原因，兩個集合完全一樣，說明其中的元素構成完全一致。元素的構成一致又有兩種可能，第一種是重復的獲取，比如[1, 3]，我們先拿1再拿3和先拿3再拿1本質上是一樣的。還有一種可能是元素的重復導致的集合重復，比如[1, 3]假如我們候選的1不止一個，那么拿不同的1也會被認為是不同的方案。針對第一種情況出現的重復非常簡單，我們可以對元素進行排序，之后限定拿取元素的順序。只能從左拿到右，不能先拿右邊的元素再回頭拿左邊的元素，這樣就禁止了第一種情況導致的重復。這個方法我們曾經在很多問題當中用到過，就不詳細介紹了。下面來說說第二種情況，就是重復元素導致的重復集合。這一點需要結合代碼來仔細說明，我們來看一段經典的搜索代碼：

def?dfs(cur, subset):????for?i in?range(cur, n):
????????nxt = subset + [nums[i]]
????????ret.append(nxt)
????????dfs(i+1, nxt)

這一段是一個經典的搜索代碼，我們在for循環當中執行的其實是一個枚舉操作，也就是枚舉這一輪我們要拿取哪一個元素。這里我們限制了選擇的范圍只能在上一次選擇元素的右側，也就是上文當中說的針對第一種情況的方案。假設我們當前候選的元素是[1, 1, 3, 3]，這里雖然有4個元素，但是值得我們搜索的其實只有兩個，就是1和3。因為第二個1和第二個3都沒有任何用處，只會導致結果重復。并且假設我們希望得到[1, 1]這樣的結果，只能通過拿取左側的1實現。也就是說如果出現重復的元素，我們只需要考慮第一個出現的，其余都沒有考慮的必要。為了更加形象， 我們畫出這一段的搜索樹。這里我們為了簡化圖示，只畫了[1, 1, 3]三個數的情況。可以看出我們選第一個1和第二個1，都構建出了[1, 3]這個集合，這是重復的。并且我們可以發現第二個1的所有情況第一個1都已經包括了，所以這一整個分支都是多余的，可以剪掉。最后，我們把上面的細節全部串起來寫出代碼：

class?Solution:def?subsetsWithDup(self, nums: List[int])?-> List[List[int]]:# 對元素排序，將重復的元素挨在一起
????????nums = sorted(nums)
????????ret = [[]]
????????n = len(nums)def?dfs(cur, subset):????# 上一次選擇的元素，一開始置為None
????????????last = Nonefor?i in?range(cur, n):if?i == cur or?nums[i] != last:# 存儲集合
????????????????????nxt = subset + [nums[i]]
????????????????????ret.append(nxt)# 更新last
????????????????????last = nums[i]
????????????????????dfs(i+1, nxt)
????????dfs(0, [])return?ret

到這里，我們關于這道題的介紹就結束了。從代碼上來看，這道題的代碼不長，涉及到需要推理的細節也并不多，總體的難度并不大。但作為一道搜索問題，它仍然非常有價值。如果你能自己思考推導得出正確的遞歸代碼，那么說明你對遞歸的理解已經可以算是合格了，所以這題也非常適合面試，要準備找工作的小伙伴，可以仔細刷刷。好了，今天的文章就到這里，如果覺得有所收獲，請順手點個在看或者轉發吧，你們的支持是我最大的動力。

上期推文：

LeetCode50-80題匯總，速度收藏！LeetCode刷題實戰81：搜索旋轉排序數組 IILeetCode刷題實戰82：刪除排序鏈表中的重復元素 IILeetCode刷題實戰83：刪除排序鏈表中的重復元素LeetCode刷題實戰84：?柱狀圖中最大的矩形LeetCode刷題實戰85：最大矩形LeetCode刷題實戰86：分隔鏈表LeetCode刷題實戰87：擾亂字符串LeetCode刷題實戰88：合并兩個有序數組LeetCode刷題實戰89：格雷編碼

總結

以上是生活随笔為你收集整理的子集和问题 算法_LeetCode刷题实战90：子集 II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。