90. Subsets II （DFS）

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.

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

思路一：

这次输入数组允许有重复项，其他条件都不变，只需要在之前那道题解法的基础上稍加改动便可以做出来，我们先来看非递归解法，拿题目中的例子[1 2 2]来分析，根据之前 Subsets 子集合 里的分析可知，当处理到第一个2时，此时的子集合为[], [1], [2], [1, 2]，而这时再处理第二个2时，如果在[]和[1]后直接加2会产生重复，所以只能在上一个循环生成的后两个子集合后面加2，发现了这一点，题目就可以做了，我们用last来记录上一个处理的数字，然后判定当前的数字和上面的是否相同，若不同，则循环还是从0到当前子集的个数，若相同，则新子集个数减去之前循环时子集的个数当做起点来循环，这样就不会产生重复了

var subsetsWithDup = function(nums) {
            nums.sort((a,b)=>a-b);
            var res=[];
            res[0]=[];
            var size=1;
            var last=nums[0]
            for (var i = 0; i < nums.length; i++) {
                //var n=res.length;
                var temp=[];
                if(last != nums[i]){
                    last=nums[i];
                    size=res.length;
                }
                var newSize=res.length;
                for (var m = newSize-size; m < newSize; m++) {
                   temp[m]=res[m].concat();
                }
                
                for (var j = newSize-size; j < newSize; j++) {
                    temp[j].push(nums[i]);
                    res.push(temp[j])
                }
            }
            return res;
        };

思路二：

对于递归的解法，根据之前 Subsets 子集合 里的构建树的方法，在处理到第二个2时，由于前面已经处理了一次2，这次我们只在添加过2的[2] 和 [1 2]后面添加2，其他的都不添加，代码只需在原有的基础上增加一句话，while (nums[i] == nums[i + 1]) ++i; 这句话的作用是跳过树中为X的叶节点，因为它们是重复的子集，应被抛弃。代码如下：

 var subsetsWithDup = function(nums) {
            //深度优先搜索算法
            if (nums.length === 0) return [];
            var res = [];
            var out = [];
            nums.sort((a, b) => a - b);
            getSubsets(nums, 0, out, res);
            return res;

            function getSubsets(nums, pos, out, res) {
                var tmp = out.concat();
                res.push(tmp);
                for (var i = pos; i < nums.length; i++) {
                    out.push(nums[i]);
                    getSubsets(nums, i + 1, out, res);
                    out.pop();
                    while (i + 1 < nums.length && nums[i] == nums[i + 1]) ++i;
                }

            }


        };