算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從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.
題意
給定一個可能包含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
輸入: [1,2,2]
輸出:
[
??[2],
??[1],
??[1,2,2],
??[2,2],
??[1,2],
??[]
]
解題
https://www.cnblogs.com/techflow/p/13489811.html題解
全排列的問題也好，獲取子集也好，這些問題都已經(jīng)算是老生常談了，我們之前做過不少。這些問題經(jīng)過轉(zhuǎn)化之后，本質(zhì)上還是搜索問題。我們在樣本空間當(dāng)中搜索所有合法的解，存儲起來。這道題的前身LeetCode78題用的正解也是搜索的解法，對于使用搜索算法來解這道題問題不大，但問題是針對數(shù)組當(dāng)中的重復(fù)元素我們應(yīng)該怎么樣來處理。最簡單也是最容易想到的方法當(dāng)然是先把所有的子集全部找到之后，我們再進(jìn)行去重。如果采用這樣的方法，還有一個便利是我們可以不用遞歸，而是可以通過二進(jìn)制枚舉的方法獲取所有的子集。但也有一個問題，問題就是復(fù)雜度。我們把集合當(dāng)中的每一個數(shù)字都看成是獨(dú)立的，那么對于每一個數(shù)字來說都有取和不取兩種方案。對于n個數(shù)字來說，方案總數(shù)當(dāng)然就是。并且我們還需要對這個集合進(jìn)行去重，這帶來的開銷可想而知。當(dāng)然針對這個問題我們也有解決方案比如可以用hash算法將一個集合hash成一個數(shù)，如果hash值一樣說明集合的構(gòu)成相同。這樣我們就可以通過對數(shù)字去重來實(shí)現(xiàn)集合去重了。但這樣仍然不是完美的，首先hash算法也不是百分百可靠的，也可能會出現(xiàn)hash值碰撞的情況。其次，這種方案的實(shí)現(xiàn)復(fù)雜度也很大，我們找出所有集合之后再通過hash算法進(jìn)行過濾，整個過程非常麻煩。既然事后找補(bǔ)不靠譜，那么我們可以試著事前避免。也就是說我們在搜索所有子集的時候就設(shè)計(jì)一種機(jī)制可以過濾掉重復(fù)的集合或者是保證重復(fù)的集合不會出現(xiàn)。我們可以分析一下重復(fù)的集合出現(xiàn)的原因，兩個集合完全一樣，說明其中的元素構(gòu)成完全一致。元素的構(gòu)成一致又有兩種可能，第一種是重復(fù)的獲取，比如[1, 3]，我們先拿1再拿3和先拿3再拿1本質(zhì)上是一樣的。還有一種可能是元素的重復(fù)導(dǎo)致的集合重復(fù)，比如[1, 3]假如我們候選的1不止一個，那么拿不同的1也會被認(rèn)為是不同的方案。針對第一種情況出現(xiàn)的重復(fù)非常簡單，我們可以對元素進(jìn)行排序，之后限定拿取元素的順序。只能從左拿到右，不能先拿右邊的元素再回頭拿左邊的元素，這樣就禁止了第一種情況導(dǎo)致的重復(fù)。這個方法我們曾經(jīng)在很多問題當(dāng)中用到過，就不詳細(xì)介紹了。下面來說說第二種情況，就是重復(fù)元素導(dǎo)致的重復(fù)集合。這一點(diǎn)需要結(jié)合代碼來仔細(xì)說明，我們來看一段經(jīng)典的搜索代碼：def?dfs(cur, subset):????
????for?i in?range(cur, n):
????????nxt = subset + [nums[i]]
????????ret.append(nxt)
????????dfs(i+1, nxt)
這一段是一個經(jīng)典的搜索代碼，我們在for循環(huán)當(dāng)中執(zhí)行的其實(shí)是一個枚舉操作，也就是枚舉這一輪我們要拿取哪一個元素。這里我們限制了選擇的范圍只能在上一次選擇元素的右側(cè)，也就是上文當(dāng)中說的針對第一種情況的方案。假設(shè)我們當(dāng)前候選的元素是[1, 1, 3, 3]，這里雖然有4個元素，但是值得我們搜索的其實(shí)只有兩個，就是1和3。因?yàn)榈诙€1和第二個3都沒有任何用處，只會導(dǎo)致結(jié)果重復(fù)。并且假設(shè)我們希望得到[1, 1]這樣的結(jié)果，只能通過拿取左側(cè)的1實(shí)現(xiàn)。也就是說如果出現(xiàn)重復(fù)的元素，我們只需要考慮第一個出現(xiàn)的，其余都沒有考慮的必要。為了更加形象， 我們畫出這一段的搜索樹。這里我們?yōu)榱撕喕瘓D示，只畫了[1, 1, 3]三個數(shù)的情況。可以看出我們選第一個1和第二個1，都構(gòu)建出了[1, 3]這個集合，這是重復(fù)的。并且我們可以發(fā)現(xiàn)第二個1的所有情況第一個1都已經(jīng)包括了，所以這一整個分支都是多余的，可以剪掉。最后，我們把上面的細(xì)節(jié)全部串起來寫出代碼：class?Solution:
????def?subsetsWithDup(self, nums: List[int])?-> List[List[int]]:
????????# 對元素排序，將重復(fù)的元素挨在一起
????????nums = sorted(nums)
????????ret = [[]]
????????n = len(nums)
????????
????????def?dfs(cur, subset):????
????????????# 上一次選擇的元素，一開始置為None
????????????last = None
????????????for?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
到這里，我們關(guān)于這道題的介紹就結(jié)束了。從代碼上來看，這道題的代碼不長，涉及到需要推理的細(xì)節(jié)也并不多，總體的難度并不大。但作為一道搜索問題，它仍然非常有價值。如果你能自己思考推導(dǎo)得出正確的遞歸代碼，那么說明你對遞歸的理解已經(jīng)可以算是合格了，所以這題也非常適合面試，要準(zhǔn)備找工作的小伙伴，可以仔細(xì)刷刷。好了，今天的文章就到這里，如果覺得有所收獲，請順手點(diǎn)個在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動力。
