# Subsets

### 描述​

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],  []]

### 递归​

#### 增量构造法​

// Subsets// 增量构造法，深搜，时间复杂度O(2^n)，空间复杂度O(n)public class Solution {    public List<List<Integer>> subsets(int[] nums) {        Arrays.sort(nums); // 输出要求有序        List<List<Integer>> result = new ArrayList<>();        List<Integer> path = new ArrayList<>();        subsets(nums, path, 0, result);        return result;    }    private static void subsets(int[] nums, List<Integer> path, int step,                                List<List<Integer>> result) {        if (step == nums.length) {            result.add(new ArrayList<Integer>(path));            return;        }        // 不选nums[step]        subsets(nums, path, step + 1, result);        // 选nums[step]        path.add(nums[step]);        subsets(nums, path, step + 1, result);        path.remove(path.size() - 1);    }}

#### 位向量法​

// Subsets// 位向量法，深搜，时间复杂度O(2^n)，空间复杂度O(n)public class Solution {    public List<List<Integer>> subsets(int[] nums) {        Arrays.sort(nums);  // 输出要求有序        List<List<Integer>> result = new ArrayList<>();        boolean[] selected = new boolean[nums.length];        subsets(nums, selected, 0, result);        return result;    }    private static void subsets(int[] nums, boolean[] selected, int step,                        List<List<Integer>> result) {        if (step == nums.length) {            ArrayList<Integer> subset = new ArrayList<>();            for (int i = 0; i < nums.length; i++) {                if (selected[i]) subset.add(nums[i]);            }            result.add(subset);            return;        }        // 不选S[step]        selected[step] = false;        subsets(nums, selected, step + 1, result);        // 选S[step]        selected[step] = true;        subsets(nums, selected, step + 1, result);    }}

### 迭代​

#### 增量构造法​

// Subsets// 迭代版，时间复杂度O(2^n)，空间复杂度O(1)public class Solution {    public List<List<Integer>> subsets(int[] nums) {        Arrays.sort(nums); // 输出要求有序        List<List<Integer>> result = new ArrayList<>();        result.add(new ArrayList<>()); // empty subset        for (int elem : nums) {            final int n = result.size();            for (int i = 0; i < n; ++i) { // copy itself                result.add(new ArrayList<>(result.get(i)));            }            for (int i = n; i < result.size(); ++i) {                result.get(i).add(elem);            }        }        return result;    }}

#### 二进制法​

// Subsets// 二进制法，时间复杂度O(2^n)，空间复杂度O(1)public class Solution {    public List<List<Integer>> subsets(int[] nums) {        Arrays.sort(nums); // 输出要求有序        List<List<Integer>> result = new ArrayList<>();        final int n = nums.length;        ArrayList<Integer> v = new ArrayList<>();        for (int i = 0; i < 1 << n; i++) {            for (int j = 0; j < n; j++) {                if ((i & 1 << j) > 0) v.add(nums[j]);            }            result.add(new ArrayList<>(v));            v.clear();        }        return result;    }}