Given a set of distinct integers, nums, 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 nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
换句话说，就是求数组的所有子数组
有两种思路：递归和非递归
思路1：递归方法（放与不放）
IMG_20170429_171634.jpg
如草图所示，每一步都是放与不放的问题，最后所有的子节点就是我们所求，可以采用深度优先算法
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
dfs(res, temp, nums, 0);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> temp, int[] nums, int j) {
res.add(new ArrayList<>(temp));
for(int i=j;i<nums.length;i++){
//放入num[i]
temp.add(nums[i]);
//继续递归
dfs(res,temp,nums,i+1);
//不放入num[i](采用的删除)
temp.remove(temp.size()-1);
}
}
思路2：非递归算法
可以用递推的思想，观察S=[], S =[1], S = [1, 2] 时解的变化。
![D}K_O8RW]QM6FPW7HZRIH0A.png](http://upload-images.jianshu.io/upload_images/2026329-bd4ca4336dd8c635.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
可以发现S=[1, 2] 的解就是 把S = [1]的所有解末尾添上2，然后再并上S = [1]里面的原有解。所以思路就是先把前次的结果取出来，再加上num[i]，再加入结果中
public List<List<Integer>> subsets2(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
res.add(new ArrayList<Integer>());//先要加一个空值
// ①从数组中取出每个元素
for (int num : nums) {
int size = res.size();
for (int i = 0; i < size; i++) {
// ②逐一取出中间结果集
List<Integer> temp = new ArrayList<>(res.get(i));
// ③将 num 放入中间结果集
temp.add(num);
// ④加入到结果集中
res.add(temp);
}
}
return res;
}
