78.Subsets (M)

https://leetcode.com/problems/subsets/

1.Description(Medium)

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

Notice

• Elements in a subset must be in _non-descending _order.

• The solution set must not contain duplicate subsets.

Example

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

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

2.Code

3种解法：http://bangbingsyb.blogspot.ca/2014/11/leetcode-subsets-i-ii.html

Version 1：DFS+Backtracking

与combination/combination sum I, II思路一样。区别在于单层扫描时不用跳过重复数字，而在进入下一层递归前就需要把当前subset压入结集中。主要递推关系就是假设函数返回递归集合，现在加入一个新的数字，我们如何得到包含新数字的所有子集。其实就是在原有的集合中对每集合中的每个元素都加入新元素得到子集，然后放入原有集合中（原来的集合中的元素不用删除，因为他们也是合法子集）。而结束条件就是如果没有元素就返回空集（注意空集不是null，而是没有元素的数组）就可以了。时间和空间都是取决于结果的数量，也就是O(2^n)

//version 2：DFS
    public ArrayList<ArrayList<Integer>> subsets(int[] nums){
        ArrayList<ArrayList<Integer>> result=new ArrayList<>();
        if(nums==null || nums.length==0){
            return result;
        }
        ArrayList<Integer> path=new ArrayList<Integer>();
        Arrays.sort(nums);
        dfs(nums,0,path,result);
        return result;        
    }

    public void dfs(int[] nums,int startindex,ArrayList<Integer> path,ArrayList<ArrayList<Integer>> result){
        result.add(new ArrayList<Integer>(path));
        for(int i=startindex;i<nums.length;i++){
            path.add(nums[i]);
            dfs(nums,i+1,path,result);
            path.remove(path.size()-1);
        }

    }

Version 2: Non-recursive:

非递归解法的思路和递归是一样的，只是没有回溯过程，也就是自无到有的一个个元素加进来，然后构造新的子集加入结果集中

//Version 1: Non-recursive:把每个path拿出来加入一个新元素。
    public ArrayList<ArrayList<Integer>> subsets(int[] nums){
        ArrayList<ArrayList<Integer>> result=new ArrayList<>();
        //记得先把空集加进去
        result.add(new ArrayList<Integer>());
        if(nums==null || nums.length==0){
            return result;
        }
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            int size=result.size();
            for(int j=0;j<size;j++){
                ArrayList<Integer> list=new ArrayList<Integer>(result.get(j));
                list.add(nums[i]);
                result.add(list);
            }
        }
        return result;
    }

//No-recursive:Given a set S of n distinct integers, 
    //there is a relation between Sn and Sn-1. 
    //The subset of Sn-1 is the union of {subset of Sn-1} and {each element in Sn-1 + one more element}. 
    //Therefore, a Java solution can be quickly formalized.
public ArrayList<ArrayList<Integer>> subsets(int[] nums) {

        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        //ArrayList<Integer> list=new ArrayList<Integer>();

        if(nums==null || nums.length==0){
            return result;
        }

        Arrays.sort(nums);

        for(int i=0;i<nums.length;i++)
        {
            ArrayList<ArrayList<Integer>> temp=new ArrayList<ArrayList<Integer>>();

            //get sets that are already in result
            for(ArrayList<Integer> a:result)
            {
                temp.add(new ArrayList<Integer>(a));//store and copy
            }

            //add nums[i] to existing sets
            for(ArrayList<Integer> b:temp)
            {
                b.add(nums[i]);
            }

            //add nums[i] only as a set
            ArrayList<Integer> single=new ArrayList<Integer>();
            single.add(nums[i]);
            temp.add(single);

            //every loop temp is a set of all new added
            result.addAll(temp);          
        }

        result.add(new ArrayList<Integer>());// add an empty set
        return result;
    }

Version 3: Bit manipulation

基本的想法是，用bit位来表示这一位的number要不要取，第一位有1，0即取和不取2种可能性。所以只要把0到N种可能

都用bit位表示，再把它转化为数字集合，就可以了。

由于S[0: n-1]组成的每一个subset，可以看成是对是否包含S[i]的取舍。S[i]只有两种状态，包含在特定subset内，或不包含。所以subset的数量总共有2^n个。所以可以用0~2^n-1的二进制来表示一个subset。二进制中每个0/1表示该位置的S[i]是否包括在当前subset中。

http://www.jiuzhang.com/solutions/subsets/ Version 4:

https://mp.weixin.qq.com/s/qT6WgR6Qwn7ayZkI3AineA

第一个解法是利用数学归纳的思想：假设我现在知道了规模更小的子问题的结果，如何推导出当前问题的结果呢？

具体来说就是，现在让你求 [1,2,3] 的子集，如果你知道了 [1,2] 的子集，是否可以推导出 [1,2,3] 的子集呢？先把 [1,2] 的子集写出来瞅瞅：

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

你会发现这样一个规律：

subset([1,2,3]) - subset([1,2])

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

而这个结果，就是把 sebset([1,2]) 的结果中每个集合再添加上 3。

换句话说，如果 A = subset([1,2]) ，那么：

subset([1,2,3])

= A + [A[i].add(3) for i = 1..len(A)]

这就是一个典型的递归结构嘛，[1,2,3] 的子集可以由 [1,2] 追加得出，[1,2] 的子集可以由 [1] 追加得出，base case 显然就是当输入集合为空集时，输出子集也就是一个空集。

翻译成代码就很容易理解了：

vector<vector<int>> subsets(vector<int>& nums) {    // base case，返回一个空集    if (nums.empty()) return {{}};    // 把最后一个元素拿出来    int n = nums.back();    nums.pop_back();    // 先递归算出前面元素的所有子集    vector<vector<int>> res = subsets(nums);    int size = res.size();    for (int i = 0; i < size; i++) {        // 然后在之前的结果之上追加        res.push_back(res[i]);        res.back().push_back(n);    }    return res;}

这个问题的时间复杂度计算比较容易坑人。我们之前说的计算递归算法时间复杂度的方法，是找到递归深度，然后乘以每次递归中迭代的次数。对于这个问题，递归深度显然是 N，但我们发现每次递归 for 循环的迭代次数取决于 res 的长度，并不是固定的。

根据刚才的思路，res 的长度应该是每次递归都翻倍，所以说总的迭代次数应该是 2^N。或者不用这么麻烦，你想想一个大小为 N 的集合的子集总共有几个？2^N 个对吧，所以说至少要对 res 添加 2^N 次元素。

那么算法的时间复杂度就是 O(2^N) 吗？还是不对，2^N 个子集是 push_back 添加进 res 的，所以要考虑 push_back 这个操作的效率：

vector<vector<int>> res = ...for (int i = 0; i < size; i++) {    res.push_back(res[i]); // O(N)    res.back().push_back(n); // O(1)}

因为 res[i] 也是一个数组呀，push_back 是把 res[i] copy 一份然后添加到数组的最后，所以一次操作的时间是 O(N)。

综上，总的时间复杂度就是 O(N*2^N)，还是比较耗时的。

空间复杂度的话，如果不计算储存返回结果所用的空间的，只需要 O(N) 的递归堆栈空间。如果计算 res 所需的空间，应该是 O(N*2^N)。

第二种通用方法就是回溯算法。旧文「回溯算法详解」写过回溯算法的模板：

result = []def backtrack(路径, 选择列表):    if 满足结束条件:        result.add(路径)        return    for 选择 in 选择列表:        做选择        backtrack(路径, 选择列表)        撤销选择

只要改造回溯算法的模板就行了：

vector<vector<int>> res;vector<vector<int>> subsets(vector<int>& nums) {    // 记录走过的路径    vector<int> track;    backtrack(nums, 0, track);    return res;}void backtrack(vector<int>& nums, int start, vector<int>& track) {    res.push_back(track);    // 注意 i 从 start 开始递增    for (int i = start; i < nums.size(); i++) {        // 做选择        track.push_back(nums[i]);        // 回溯        backtrack(nums, i + 1, track);        // 撤销选择        track.pop_back();    }}

可以看见，对 res 的更新是一个前序遍历，也就是说，res 就是树上的所有节点：

二、组合

输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合。

vector<vector<int>> combine(int n, int k);

比如输入 n = 4, k = 2，输出如下结果，顺序无所谓，但是不能包含重复（按照组合的定义，[1,2] 和 [2,1] 也算重复）：

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

这就是典型的回溯算法，k 限制了树的高度，n 限制了树的宽度，直接套我们以前讲过的回溯算法模板框架就行了：

vector<vector<int>>res;vector<vector<int>> combine(int n, int k) {    if (k <= 0 || n <= 0) return res;    vector<int> track;    backtrack(n, k, 1, track);    return res;}void backtrack(int n, int k, int start, vector<int>& track) {    // 到达树的底部    if (k == track.size()) {        res.push_back(track);        return;    }    // 注意 i 从 start 开始递增    for (int i = start; i <= n; i++) {        // 做选择        track.push_back(i);        backtrack(n, k, i + 1, track);        // 撤销选择        track.pop_back();    }}

backtrack 函数和计算子集的差不多，区别在于，更新 res 的地方是树的底端。