## 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) {
return;
}
// 不选nums[step]
subsets(nums, path, step + 1, result);
// 选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++) {
}
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<>();
for (int elem : nums) {
final int n = result.size();
for (int i = 0; i < n; ++i) { // copy itself
}
for (int i = n; i < result.size(); ++i) {
}
}
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]);
}