# 0078. Subsets
###### tags: `Leetcode` `Medium` `回溯` `DFS`
Link: https://leetcode.com/problems/subsets/

## Code
### 方法一
直接遍历，初始状态是只有一个子集是空集合，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i < len; i++) {
            for (int j = res.size() - 1; j >= 0; j--) {
                ArrayList<Integer> tmp = new ArrayList<>((ArrayList<Integer>) res.get(j));
                tmp.add(nums[i]);
                res.add(tmp);
            }
        }
        return res;
    }
}

### 方法二：回溯
#### 回溯一

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> ele = new ArrayList<>();
        dfsSubsets(res, 0, len, nums, ele);
        return res;
    }

    private void dfsSubsets(List<List<Integer>> res, int index, int len, int[] nums, List<Integer> ele) {
        res.add(new ArrayList<>(ele));
        for (int i = index; i < len; i++) {
            ele.add(nums[i]);
            dfsSubsets(res, i + 1, len, nums, ele);
            ele.remove(ele.size() - 1);
        }
    }

}

#### 回溯二

class Solution {

    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> ele = new ArrayList<>();
        res.add(new ArrayList<>());
        dfsSubsets(res, 0, len, nums, ele);
        return res;
    }
    private void dfsSubsets(List<List<Integer>> res, int index, int len, int[] nums, List<Integer> ele) {
        if (index == len) return;
        for (int i = index; i < len; i++) {
            ele.add(nums[i]);
            res.add(new ArrayList<>(ele));
            dfsSubsets(res, i + 1, len, nums, ele);
            ele.remove(ele.size() - 1);
        }
    }
}

### 方法三：二进制数

Lexicographic (Binary Sorted) Subsets 很巧妙的方法
建立一个和nums一样大小的阵列，里面只放0跟1，1代表这个位置对应的nums这个位置的值，要被放在现有的subset里面，0代表不放。（The idea is that we map each subset to a bitmask of length n, where 1 on the ith position in bitmask means the presence of nums[i] in the subset, and 0 means its absence.）
那么现在我们只要产生00.....00到11...11的数，这里需要注意，因为**要有left zero padding**
这个方法没有用c++写的原因是它很难建立这样的阵列

    bitset<nums.size()> binary_num (i);
    string bitmask = binary_num.to_string();

bitset后面的<>里面必须放整数，不能放变量，即使是用```const int n = nums.size()```也不行。

$n=3$，全集${3,2,4}$

二进制数 | 子集
-------|-----
000 | {}
001 | {3}
010 | {2}
011 | {3,2}
100 | {4}
101 | {4,3}
110 | {4,2}
111 | {3,2,4}

class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}

时间复杂度$O(n\cdot 2^n)$
空间复杂度$O(n)$