原题传送门

1. 题目描述

2. Solution 1

**1、思路分析 **
递归使用回溯法。

2、代码实现

package Q0099.Q0078Subsets;  import org.junit.Test;  import java.util.ArrayList; import java.util.Arrays; import java.util.List;  // Recursive (Backtracking) public class Solution1 {     /*         Time: O(n * 2^n)         Space: O(n/2 * 2^n) ~= O(n * 2^n)      */     public List<List<Integer>> subsets(int[] nums) {         List<List<Integer>> list = new ArrayList<>();         Arrays.sort(nums);         backtrack(list, new ArrayList<>(), nums, 0);         return list;     }      private void backtrack(List<List<Integer>> list, ArrayList<Integer> curRes, int[] nums, int start) {         list.add(new ArrayList<>(curRes));         for (int i = start; i < nums.length; i++) {             curRes.add(nums[i]);             backtrack(list, curRes, nums, i + 1);             curRes.remove(curRes.size() - 1);         }     } } 

3、复杂度分析
时间复杂度: O(n * 2^n)
空间复杂度: O(n/2 * 2^n) ~= O(n * 2^n)

3. Solution 2

1、思路分析
迭代，以nums=[1, 2, 3]为例。处理步骤如下
1> 初始时，res = [[]].
2> 把nums[0]=1加到res的所有成员得，res = [[], [1]].
3> 把nums[1]=2加到res的所有成员得，res= [[], [1],[2], [1,2]].
4> 把nums[2]=3加到res的所有成员得，res=[[3], [1,3],[2,3], [1,2,3]].

2、代码实现

package Q0099.Q0078Subsets;  import java.util.ArrayList; import java.util.List;  /*     Iterative     Using [1, 2, 3] as an example, the iterative process is like:     1) initially, one empty subset [[]]     2) Adding 1 to []: [[], [1]]     3) Adding 2 to [] and [1]: [[], [1], [2], [1, 2]]     4) Adding 3 to [], [1], [2] and [1, 2]: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]  */ public class Solution2 {     public List<List<Integer>> subsets(int[] nums) {         List<List<Integer>> subs = new ArrayList<>();         subs.add(new ArrayList<>());         for (int num : nums) {             int n = subs.size();             for (int i = 0; i < n; i++) {                 subs.add(new ArrayList<>(subs.get(i)));                 subs.get(subs.size() - 1).add(num);             }         }         return subs;     } } 

3、复杂度分析
时间复杂度: O(n * 2^n)
空间复杂度: O(n/2 * 2^n) ~= O(n * 2^n)

4. Solution 3

1、思路分析
以nums=[1, 2, 3]为例，nums长度为3，则共有2 ^ 3 =8个子集，这8个子集编号为 0 ~ 7，用3个bit来编码为:

做一个映射，用上表的Binary[i] -> nums[i]，用Binary[i]的取值代表nums[i]是否出现。
如:
result idx=0，Binary = {0, 0, 0}表示 nums[0]、nums[1]、nums[2]均不出现，即 curResult = []。
result idx=1，Binary = {0, 0, 1}表示 nums[0]出现，nums[1]、nums[2]均不出现，即 curResult = [1]。
...
result idx=6，Binary = {1, 1, 0}表示 nums[0]不出现，nums[1]、nums[2]出现，即 curResult = [2, 3]。
result idx=7，Binary = {1, 1, 1}表示 nums[0]、nums[1]、nums[2]出现，即 curResult = [1, 2, 3]。

2、代码实现

package Q0099.Q0078Subsets;  import org.junit.Test;  import java.util.ArrayList; import java.util.List;  /*     Bit Manipulation     To give all the possible subsets, we just need to exhaust all the possible combination of the numbers. And each     number has only two possibilities: either in or nor in a subset. And this can be represented using a bit.      Using [1, 2, 3] as an example, 1 appears once in every two consecutive subsets, 2 appears twice in every four     consecutive subsets, and 3 appears four times in every eight subsets(initially all subsets are empty).     2 ^ 3 = 8 总共有8个子集     0 -> 000     1 -> 001     2 -> 010     3 -> 011     4 -> 100     5 -> 101     6 -> 110     7 -> 111  */ public class Solution3 {      @Test     public void test1() {         int[] nums = {1, 2, 3};         List<List<Integer>> result = subsets(nums);         System.out.println(result);     }      public List<List<Integer>> subsets(int[] nums) {         int n = nums.length, p = 1 << n;         List<List<Integer>> subs = new ArrayList<>();         for (int i = 0; i < p; i++) subs.add(new ArrayList<>());          for (int i = 0; i < p; i++) {             for (int j = 0; j < n; j++) {                 if (((i >> j) & 1) > 0) {                     subs.get(i).add(nums[j]);                 }             }         }         return subs;     } } 

3、复杂度分析
时间复杂度: