Subsets

01/22/2018

• Each level add the subset containing its parent node to the result at the beginning. 
• Have to remove the previous added number, for instance, [1,2], when to go [1.3] needs to remove 2. 

Solution:

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> res=new ArrayList<>();
        if(nums==null)
        {
            return null;
        }
        //Arrays.sort(nums);
        List<Integer> subset=new ArrayList<Integer>();
        search(subset, 0, res, nums);
        
        return res;
    }
    
    private void search(List<Integer> subset, int startIndex, List<List<Integer>> res, int[] nums)
    {
        res.add(new ArrayList<>(subset));
        for (int i = startIndex; i < nums.length; i++) {
            subset.add(nums[i]);
            search(subset, i+1, res, nums);
            subset.remove(subset.size() - 1);
        }
    }
}

--------------------------------------------------------------------------------------------------------------------------


思路：
画个图分解一下

规律就是以母节点为起始，向数组后面走，每一层只加一个数。可以用DFS来做。

实现：
2个注意的地方
1. java 初始化ArrayList的时候不能包含ArrayList,比如new ArrayList<ArrayList<Integer>>()，直接new ArrayList<>()就好了。
2. 添加结果的时候需要用deep copy, res.add(new ArrayList<Integer>(subset)); 加值进去而不是reference。