【題目描述】

我們擁有十載網(wǎng)頁設(shè)計和網(wǎng)站建設(shè)經(jīng)驗，從網(wǎng)站策劃到網(wǎng)站制作，我們的網(wǎng)頁設(shè)計師為您提供的解決方案。為企業(yè)提供網(wǎng)站制作、成都網(wǎng)站制作、微信開發(fā)、微信平臺小程序開發(fā)、手機網(wǎng)站開發(fā)、HTML5、等業(yè)務(wù)。無論您有什么樣的網(wǎng)站設(shè)計或者設(shè)計方案要求，我們都將富于創(chuàng)造性的提供專業(yè)設(shè)計服務(wù)并滿足您的需求。

Given a list of numbers that may has duplicate numbers, return all possible subsets

Notice:Each element in a subset must be in non-descending order.The ordering between two subsets is free.The solution set must not contain duplicate subsets.

給定一個可能具有重復(fù)數(shù)字的列表，返回其所有可能的子集

注意:子集中的每個元素都是非降序的;兩個子集間的順序是無關(guān)緊要的;解集中不能包含重復(fù)子集

【題目鏈接】

http://www.lintcode.com/en/problem/subsets-ii/

【題目解析】

經(jīng)典的DFS問題，如果有跟過九章微博的同學 應(yīng)該會相當熟悉這個套路，跟前一個題目SubSet的區(qū)別是，有了重復(fù)的問題。怎么解決呢？

很簡單。在每一次選數(shù)字的時候，只選第一個重復(fù)的數(shù)字，不選后面的，這樣就不會有重復(fù)的set出現(xiàn)了。這里肯定有同學問了，如果你只選第一個，那222這種組合怎么弄出來？答案是：用遞歸時就不要考慮太多，只要考慮當前的情況。

例子： 1 2 2 2 2 3 4

那么你得到2 2 2 的過程是三層遞歸，每一層 都只選當前index開始的第一個2，所以2 2 2 還是可以組出來的。而且不會組出重復(fù)的，因為每一層遞歸你沒有考慮重復(fù)，這就可以了。

還是要記住遞歸的精髓：考慮本層遞歸就好，別想太多

【答案鏈接】

https://www.jiuzhang.com/solutions/subsets-ii/