子集
题目链接：https://leetcode.cn/problems/subsets/description/?envType=study-plan-v2&envId=top-100-liked
我的解答：
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); List<Integer> output = new ArrayList<>(); backtrack(nums, output, 0, nums.length, ans); return ans; } public void backtrack(int[] nums, List<Integer> output, int cur, int n, List<List<Integer>> ans){ if(cur == n){ ans.add(new ArrayList<>(output)); return; } //不选取当前位置的元素 backtrack(nums, output, cur+1, n, ans); //选取当前位置的元素 output.add(nums[cur]); backtrack(nums, output, cur+1, n, ans); //回溯 output.remove(output.size()-1); }分析：代码的时间复杂度为O(n*2^n)，空间复杂度为O(n)。解题思路：对于nums数组的每一个元素只有两种情况（选取和不选取）,递归+回溯即可简单解决此问题。
看了官方题解后的解答：
//方法一：迭代法实现子集枚举 //时间复杂度：O(n*2^n) //空间复杂度：O(1) public List<List<Integer>> subsets(int[] nums) { int n = nums.length; List<List<Integer>> ans = new ArrayList<>(); int max = 1 << n;//计算2^n for(int i=0; i<max; i++){ ans.add(new ArrayList<>()); for(int j=0; j<n; j++){ if(((1 << j) & i) != 0){ ans.get(i).add(nums[j]); } } } return ans; } //方法二：递归法实现子集枚举（方法二与我的解答基本一致） //时间复杂度：O(n*2^n)，一共2^n个状态，每种状态需要 O(n) 的时间来构造子集。 //空间复杂度：O(n) public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); List<Integer> output = new ArrayList<>(); backtrack(nums, output, 0, ans); return ans; } public void backtrack(int[] nums, List<Integer> output, int cur, List<List<Integer>> ans){ if(cur == nums.length){ ans.add(new ArrayList<>(output)); return; } //不选取当前位置的元素 backtrack(nums, output, cur+1, ans); //选取当前位置的元素 output.add(nums[cur]); backtrack(nums, output, cur+1, ans); //回溯 output.remove(output.size()-1); }分析：
1、方法一的解题思路：对于一个长度为n的集合，它的子集一共有2^n 种可能，对于数组每一个位置上的元素，只有两种状态，分别为在子集中和不在子集中，我们让0代表不在子集中，让1代表在子集中，这样对于任意一个子集，都可以用一串长度为n的01序列来表示，根据这个发现，我们只需列举0到2^n-1这些数字，他们对应的二进制就可以代表一个子集，我们只需根据二进制每一位是0还是1来决定nums数组在此位置的元素要不要加入当前子集即可。
2、方法二的解题思路与我的解答一致。
总结
- 本题可采用迭代和递归两种方法解题。
- 迭代法根据每个位置上的元素只有两种状态将子串与二进制序列联系起来。
- 注意递归方法的时间复杂度计算。
