90. Subsets II--LeetCode

Note:
Elements in a subset must be in non-descending order.
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],
  []
]
就是求子集。子集中的元素，从小到大。

分析nums=[1,2,2]：递归树

第一步 选择还是不选nums[0]:               [][1]
第二步 选择还是不选nums[1]:       [][2]          [1][1,2]
第三步 选择还是不选nums[2] : [][2]  [2][2,2]  [1][1,2]    [1,2][1,2,2] 
最后最后一共2^3=8个解，[2][1,2]重复。6个解，

发现第二步和第三步产生了，重复分枝；
         [][2]
    [][2]    [2][2,2] 
可以在这个时候合并。变成[] [2] [2,2]
最后:[][1]  +  [] [2] [2,2]
[][2][2,2]    [1][1,2][1,2,2]
在出现大量重复相同元素，可以明显缩小运算规模。
由于，leetcode要求排序。排序方法采用快排。

自己写的，递归树加剪枝。一步步合并相同的分枝。[0,1,1,1,1]这种。

   var subsetsWithDup = function(nums) {
    var  results=[];
    Array.prototype.quickSort=function(f){
        var fn=f;;
        if(f==null){
            fn=function(a,b){return a-b;}
        }//快排
        var arr=this;
        if (arr.length <= 1) { return arr; }
        var index= Math.floor(arr.length/2);
        //   var pivot = arr.splice(index,1)[0];
        var pivot = arr[index];
        var left=[];
        var right=[];
        for(var i=0;i<arr.length;i++){
            if(i==index){continue;}
            if(fn(arr[i],pivot)>0){right.push(arr[i])}
            else{left.push(arr[i])}
        }
        return left.quickSort(fn).concat([pivot], right.quickSort(fn));
    };
    function isSame(a,b){
        try{
            if(a.length!=b.length){return false;}
            for(var i=0;i< a.length;i++){
                if(a[i].constructor==Array){
                    if(isSame(a[i],b[i])){continue;}
                    else{return false;}
                }
                if(a[i]==b[i]){continue;}
                else{return false;}
            }
            return true;
        }catch(e){
            return false;
        }
    }
    function he(a,b){
        var temp=[];var same;
        for(var i=0;i< a.length;i++){
            if(isSame(same,a[i])){continue;}
            same=a[i];
            for(var j=0;j< b.length;j++){
                temp.push(a[i].concat(b[j]));
            }
        }
        //             console.log(temp);
        return temp;
    }
    for(var i=0;i<nums.length;i++){
        if(nums.length==0){break;}
        var temp = []
        var Num=nums.splice(i,1);
        i--;
        temp.push([[],Num]);
        for(var j=0;j<nums.length;j++){
            if(Num==nums[j]){
                temp.push([[],nums.splice(j,1)]);
                j--;
            }
        }
        //         console.log(temp);
        for(var k=0;k<temp.length;k++){
            if(k>0){
                temp[k]= he(temp[k-1],temp[k]);
            }
        }
        var same;
        var rsult=temp[temp.length-1]
        for(var p=0;p<rsult.length;p++){
            if(isSame(same,rsult[p])){ rsult.splice(p,1);p--;}
            same=rsult[p];
        }
        //        console.log(rsult);
        results.push(rsult)
    }
  results=  results.quickSort(function(a,b){return a[1]-b[1];})
    for(var z=0;z<results.length;z++){
        if(z>0) {
            results[z] = he(results[z - 1], results[z])
        }
    }
    console.log(results[results.length-1]);
    return results[results.length-1]
};//Runtime:216 ms

只用递归树的。到最后合并相同的解2^n。看了下leetcode上面的输入规模小，不用剪枝更快。只有在大量相同的元素时，才会大量产生相同分枝，需要剪枝。

   var subsetsWithDup = function(nums) {
       var  results=[];
       Array.prototype.quickSort=function(f){
           var fn=f;;
           if(f==null){
               fn=function(a,b){return a-b;}
           }//快排
           var arr=this;
           if (arr.length <= 1) { return arr; }
           var index= Math.floor(arr.length/2);
           //   var pivot = arr.splice(index,1)[0];
           var pivot = arr[index];
           var left=[];
           var right=[];
           for(var i=0;i<arr.length;i++){
               if(i==index){continue;}
               if(fn(arr[i],pivot)>0){right.push(arr[i])}
               else{left.push(arr[i])}
           }
           return left.quickSort(fn).concat([pivot], right.quickSort(fn));
       };
       function isSame(a,b){
           try{
               if(a.length!=b.length){return false;}
               for(var i=0;i< a.length;i++){
                   if(a[i].constructor==Array){
                       if(isSame(a[i],b[i])){continue;}
                       else{return false;}
                   }
                   if(a[i]==b[i]){continue;}
                   else{return false;}
               }
               return true;
           }catch(e){
               return false;
           }
       }
       function he(a,b){
           var temp=[];var same;

           for(var i=0;i< a.length;i++){
               if(isSame(same,a[i])){continue;}
               same=a[i];
               for(var j=0;j< b.length;j++){
                   temp.push(a[i].concat(b[j]));
               }
           }
           //             console.log(temp);
           return temp;
       }
       nums=nums.quickSort();
       var temp = [];
       for(var i=0;i<nums.length;i++){
           if(nums.length==0){break;}
           var Num=nums.slice(i,i+1);
           temp.push([[],Num]);
           if(i>0) {
               temp[i] = he(temp[i - 1], temp[i])
           }
       }
//      console.log(temp[temp.length-1])
       var same;
       var rsult=temp[temp.length-1]
       for(var p=0;p<rsult.length;p++){
           if(isSame(same,rsult[p])){ rsult.splice(p,1);p--;}
           same=rsult[p];
       }
   //    console.log(rsult)
       return rsult;

   };//Runtime: 112 ms 超过100%的javascript代码。好假

用WebWorker做测试。

var w1 =new Worker("Subsets1.js");
var w2 =new Worker("Subsets2.js");

w1.onmessage =function(evt){
    //接收worker传过来的数据函数
    console.log(evt.data);
    //输出worker发送来的数据
}

w2.onmessage =function(evt){
    //接收worker传过来的数据函数
    console.log(evt.data);
}

• 输入[4,1,0]时。2先完成
  
• 输入[4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,1,0]时。1先完成
  

证明只有在大量相同的元素时，剪枝还是有点用的。。。。