【原题】 Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example, If nums = [1,2,3], a solution is:
代码语言：javascript复制[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]【解释】 给定一个集合，求该集合的所有子集。 【思路】
思路一、DFS
想象有那么一棵树，初始树的根结点为空（假设为第零层），则没往下一层添加一个元素，树的第几层其子集就会有几个元素。使用树的深度优先遍历就可以得到所有的子集，每回溯一次，就要删除最后一个加入的结点。二刷了，刚开始还是没想出来，很是惭愧。推荐看下这里 的图片，就会很清晰了。
代码语言：javascript复制public class Solution {
public void backtrack(int[] nums,List<List<Integer>> result, ArrayList<Integer> list,int level){
result.add(new ArrayList<Integer>(list));
for(int i=level;i<nums.length;i ){//若当前层次没有超过最大高度，继续深度优先遍历，否则执行remove语句
list.add(nums[i]);
backtrack(nums,result, list,i 1);//深度优先遍历下一层
list.remove(list.size()-1);//删除最后加入的结点
}
}
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result=new ArrayList<List<Integer>>();
int num=nums.length;
//当然这里不排序也可以AC，排序从小到大看起来更顺眼？
Arrays.sort(nums);
ArrayList<Integer> list=new ArrayList<Integer>();
backtrack(nums,result, list,0);
return result;
}
}思路二、 迭代法 参考这里 以集合{1,2,3}为例。 初始化：[[]] 第一步：[[],[1]]（在上面的结果的子集上添加元素1并上面的集合） 第二步：[[],[1],[2],[1,2]]（上第二步结果上每个子集添加元素2并上面的集合） 第三步：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]（…） 代码：
代码语言：javascript复制public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result=new ArrayList<List<Integer>>();
Arrays.sort(nums);
List<Integer> list=new ArrayList<Integer>();
result.add(new ArrayList<>(list));
for(int i=0;i<nums.length;i ){
int n=result.size();//先保留size，因为后面的result的size一直在变
for(int j=0;j<n;j ){
list=new ArrayList<Integer>(result.get(j));
list.add(nums[i]);
result.add(list);
}
}
return result;
}
}思路三、位操作 同样参考上面的链接。假设有集合有n个元素，子集的个数为2n−12^{n-1}。可以把这2n−12^{n-1}元素是由n位二进制数组成的集合，每次只要看n位二进制中的哪一位为1，则指定集合包含在子集中。如i=3(011)i=3(011),集合{1,2,3}对应的二进制位为1,2,4 则此时子集为{1,2}。这个方法感觉很神奇，有木有。
代码语言：javascript复制public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> results=new ArrayList<List<Integer>>();
int length=nums.length;
for(int i=0;i<1<<length;i ){
List<Integer> result=new ArrayList<>();
for(int j=0;j<length;j ){
if((i&(1<<j))!=0)//判断第j为是否为1
result.add(nums[j]);
}
results.add(result);
}
return results;
}
}
