subsets子集合（DFS）

Given a set of distinct integers, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

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

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

思路：

最开始想到的是按长度划分，0个元素就一个[],1个元素的就遍历一遍，一个for循环，2个长度的就两个for循环遍历，依次类推，但发现复杂度太高，肯定是不行的。
可以一位一位的往上叠加，比如对于题目中给的例子[1,2,3]来说，最开始是空集，那么我们现在要处理1，就在空集上加1，为[1]，现在我们有两个[]和[1]，下面我们来处理2，我们在之前的子集基础上，每个都加个2，可以分别得到[2]，[1, 2]，那么现在所有的子集合为[], [1], [2], [1, 2]，同理处理3的情况可得[3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合

代码

var subsets = function(nums) {
    var res=[];
    res[0]=[];
    for(var i=0;i<nums.length;i++){
        var temp=res.concat();
        var n=res.length;
        for(var j=0;j<n;j++){
            temp[j].push(nums[i]);
            res.push(temp[j])
        }
    }
    return res;
};

但是结果不对，我也很绝望啊，回头再看看！
是因为没有深度复制。
正确的代码

var subsets = function(nums) {
    var res=[];
    res[0]=[];
    for(var i=0;i<nums.length;i++){
        var n=res.length;
        var temp=[];
        for(var m=0;m<n;m++){
            temp[m]=res[m].slice(0);
        }
        for(var j=0;j<n;j++){
            temp[j].push(nums[i]);
            res.push(temp[j])
        }
    }
    return res;
};

思路二：递归

相当于一种深度优先搜索，参见网友

JustDoIt的博客

，由于原集合每一个数字只有两种状态，要么存在，要么不存在，那么在构造子集时就有选择和不选择两种情况，所以可以构造一棵二叉树，左子树表示选择该层处理的节点，右子树表示不选择，最终的叶节点就是所有子集合，树的结构如下：

                       []        
                   /          \        
                  /            \     
                 /              \
              [1]                []
           /       \           /    \
          /         \         /      \        
       [1 2]       [1]       [2]     []
      /     \    /   \      /   \    / \
  [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []

var subsets = 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();
            }

        }
    
    
};

思路三：

这种解法是CareerCup书上给的一种解法，想法也比较巧妙，把数组中所有的数分配一个状态，true表示这个数在子集中出现，false表示在子集中不出现，那么对于一个长度为n的数组，每个数字都有出现与不出现两种情况，所以共有2n中情况，那么我们把每种情况都转换出来就是子集了，我们还是用题目中的例子, [1 2 3]这个数组共有8个子集，每个子集的序号的二进制表示，把是1的位对应原数组中的数字取出来就是一个子集，八种情况都取出来就是所有的子集了

image.png