摘要：題目要求可以先參考關于的這篇博客再看接下來的內容。思路一鏈表的形式我們可以通過例子，，，來說明。在遞歸中我們會將起始下標后的值依次加入當前結果集，并將結果集加入結果集數組中。如果遇到重復的數字，則繼續遍歷下一個數字，直至遍歷結束。
題目要求
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],
[]
]
可以先參考關于SubsetI的這篇博客再看接下來的內容。
這里的區別在于假設輸入的數組存在重復值，則找到所有不重復的子集。
思路一：鏈表的形式
我們可以通過例子[1，2，2，3]來說明。當我們遇到重復值時，我們可以使用一個臨時數組將所有重復值的結果臨時保存起來，在這道題目中就是[[2],[2,2]]，然后再將當前res中的結果和它一一組合成新的結果值，本例子中的當前res為[[ ],[1]]，這樣合成之后就是[[],[2],[2,2],[1,2],[1,2,2]]，從而避免產生重復的結果。
代碼如下：
public List> subsetsWithDup(int[] nums) {
List> result = new LinkedList>();
result.add(new ArrayList());
int length = nums.length;
Arrays.sort(nums);
for(int i = 0 ; i> temp = new LinkedList>();
for(List tempResult : result){
List copyTemp = new ArrayList(tempResult);
copyTemp.add(nums[i]);
temp.add(copyTemp);
}
i++;
while(i0){
List currentTemp = temp.removeFirst();
result.add(currentTemp);
List moreCurrentTemp = new ArrayList(currentTemp);
moreCurrentTemp.add(nums[i]);
temp.add(moreCurrentTemp);
}
}
result.addAll(temp);
}
return result;
}
思路二：遞歸
其實對于遞歸，應當考慮從遞歸的輸入和輸出考慮。在這里我們將遞歸的輸入為當前的結果集，當前的數組，和遍歷的起始下標。在遞歸中我們會將起始下標后的值依次加入當前結果集，并將結果集加入結果集數組中。如果遇到重復的數字，則繼續遍歷下一個數字，直至遍歷結束。思路簡單清晰，效率也很高。
public List> subsetsWithDup2(int[] nums) {
List> fnl = new ArrayList>();
Arrays.sort(nums);
helper(fnl, new ArrayList(), nums, 0);
return fnl;
}
public void helper(List> fnl, List temp, int[] nums, int start){
fnl.add(new ArrayList(temp));
for(int i =start; istart && nums[i]==nums[i-1]) continue;
temp.add(nums[i]);
helper(fnl, temp, nums, i+1 );
temp.remove(temp.size()-1);
}
}
想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/67356.html
