leetcode---Subsets

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](https://img.haomeiwen.com/i2026329/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;
    }