溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(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.
給定一個(gè)可能具有重復(fù)數(shù)字的列表，返回其所有可能的子集
注意:子集中的每個(gè)元素都是非降序的;兩個(gè)子集間的順序是無關(guān)緊要的;解集中不能包含重復(fù)子集
【題目鏈接】
http://www.lintcode.com/en/problem/subsets-ii/
【題目解析】
經(jīng)典的DFS問題，如果有跟過九章微博的同學(xué) 應(yīng)該會(huì)相當(dāng)熟悉這個(gè)套路，跟前一個(gè)題目SubSet的區(qū)別是，有了重復(fù)的問題。怎么解決呢？
很簡單。在每一次選數(shù)字的時(shí)候，只選第一個(gè)重復(fù)的數(shù)字，不選后面的，這樣就不會(huì)有重復(fù)的set出現(xiàn)了。這里肯定有同學(xué)問了，如果你只選第一個(gè)，那222這種組合怎么弄出來？答案是：用遞歸時(shí)就不要考慮太多，只要考慮當(dāng)前的情況。
例子： 1 2 2 2 2 3 4
那么你得到2 2 2 的過程是三層遞歸，每一層 都只選當(dāng)前index開始的第一個(gè)2，所以2 2 2 還是可以組出來的。而且不會(huì)組出重復(fù)的，因?yàn)槊恳粚舆f歸你沒有考慮重復(fù)，這就可以了。
還是要記住遞歸的精髓：考慮本層遞歸就好，別想太多
【答案鏈接】
https://www.jiuzhang.com/solutions/subsets-ii/
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼
