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], []]解決這個，最后先回憶一下LeetCode 78。 LeetCode 78與LeetCode 90唯一的差別是，LeetCode的輸入數(shù)組中沒有重復(fù)的數(shù)據(jù)。
LeetCode 78的一種解法的思路類似于：
public class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); ArrayList<Integer> tmp = new ArrayList<>(); Arrays.sort(nums); //首先增加空集 res.add(tmp); dfs(res,tmp,nums,0); return res; } public void dfs(List<List<Integer>> res, ArrayList<Integer> tmp, int[] nums, int pos){ for(int i=pos; i<=nums.length-1;i++){ //每增加一個新的數(shù)，都構(gòu)成一個新的子集 tmp.add(nums[i]); //將新的集合加入結(jié)果 res.add(new ArrayList<Integer>(tmp)); //進(jìn)入下一層的迭代 //避免重復(fù)，下一個加入的數(shù)，在當(dāng)前數(shù)位置的后面 dfs(res,tmp,nums,i+1); //當(dāng)前數(shù)，作為本層的結(jié)尾，已經(jīng)加入了所有的結(jié)果 //需要移除，將下一個數(shù)作為本層的結(jié)果 tmp.remove(tmp.size()-1); } }}上面代碼運(yùn)行的結(jié)果類似于：
比如，輸入集合為［1，2，3］，那么依次加入的結(jié)果類似于：[] //從空集開始，每次增加一個元素，都構(gòu)成一個新的子集[1] //第1層迭代[1,2] //第2層迭代[1,2,3] //第3層迭代 //第4層迭代，pos大于length-1，無實(shí)際操作 //回到第3層，移除3 //3后面沒有其它數(shù)了，回到第2層 //移除2[1,3] //第2層跌代，加入2后面的數(shù)3 //第3層迭代，pos大于length-1，無實(shí)際操作 //回到第2層，移除3 //3后面沒有其它數(shù)了，回到第1層 //移除1[2] //第1層跌代，加入1后面的數(shù)2[2,3] //第2層跌代，加入3 //第3層迭代，pos大于length-1，無實(shí)際操作 //回到第2層，移除3 //3后面沒有其它數(shù)了，回到第1層 //移除2[3] //第1層跌代，加入2后面的數(shù)3 //第2層迭代，pos大于length-1，無實(shí)際操作 //回到第1層，移除3 //3后面沒有其它數(shù)了，結(jié)束在LeetCode 78的基礎(chǔ)上，LeetCode 90就比較好解決了，只要避免不必要的重復(fù)就行。 代碼示例如下：
public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> res = new ArrayList<>(); ArrayList<Integer> tmp = new ArrayList<>(); Arrays.sort(nums); res.add(tmp); dfs(res,tmp,nums,0); return res; } public void dfs(List<List<Integer>> res, ArrayList<Integer> tmp, int[] num, int pos){ for(int i=pos;i<=num.length-1;i++){ tmp.add(num[i]); res.add(new ArrayList<>(tmp)); dfs(res,tmp,num,i+1); tmp.remove(tmp.size()-1); //就是額外增加了這一部分 while(i<num.length-1 && num[i]==num[i+1]) { i++; } } }}舉例如下：
假設(shè)集合為［2，3，3］，如果按照LeetCode 78中的代碼運(yùn)行，結(jié)果如下：[][2] //1層[2,3] //2層[2,3,3] //3層 //4層未實(shí)際運(yùn)行，回退到第3層，移除最后一個3 //3后沒其它數(shù)，回到第2層 //回到第2層后，移除第2個三[2,3] //然后添加最后一個3，形成重復(fù) //以下分析類似[3][3,3][3]因此，每層迭代，移除的數(shù)不能和新加入的數(shù)一致。
新聞熱點(diǎn)
疑難解答
