LeetCode(BackTracking)Subsets

2018-06-25

Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

思路：和上一道找出所有排列的题类似，我们依然采用回溯法解决。需要注意的是这个地方我们在查找集合中剩余的元素时，每一次查找都将找到的结果放入结果集中，而统计结束的条件就是找到数组中的最后一个元素，这个时候需要回退，并且在回退到还有其他路径的情况时去查找那条路径下有没有满足条件的值，有就继续增加。回溯法的逻辑很复杂，循环中嵌套着递归，导致递归中又含有循环，还需好好体会这种解题思路。难点在于：构造可以递归的辅助函数，以及边界条件的设置。

代码如下：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        backtracking(res,new ArrayList<Integer>(),nums,0);
        return res;
    }
    public void backtracking(List<List<Integer>> res,List<Integer> templist,int [] nums,int start){
        res.add(new ArrayList<>(templist));
        for(int i=start;i<nums.length;i++){
            templist.add(nums[i]);
            backtracking(res,templist,nums,i+1);
            templist.remove(templist.size()-1);
        }
    }
}

改进思路：在网上看到一个更容易理解的算法，没有利用深度搜索，也没有利用回溯法，就是单纯的数学解法。

初始给reslist中放一个空的list, 然后从1开始往里边放数，之后将增加了的list加入reslist中，接着再将下一个数依次增加到目前已经存在在reslist中的各个子的sublist中，这样，就可以遍历出所有的sublist。

While iterating through all numbers, for each new number, we can either pick it or not pick it
1, if pick, just add current number to every existing subset.
2, if not pick, just leave all existing subsets as they are.
We just combine both into our result.

For example, {1,2,3} intially we have an emtpy set as result [ [ ] ]
Considering 1, if not use it, still [ ], if use 1, add it to [ ], so we have [1] now
Combine them, now we have [ [ ], [1] ] as all possible subset

Next considering 2, if not use it, we still have [ [ ], [1] ], if use 2, just add 2 to each previous subset, we have [2], [1,2]
Combine them, now we have [ [ ], [1], [2], [1,2] ]

Next considering 3, if not use it, we still have [ [ ], [1], [2], [1,2] ], if use 3, just add 3 to each previous subset, we have [ [3], [1,3], [2,3], [1,2,3] ]
Combine them, now we have [ [ ], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ]

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> reslist = new ArrayList<>();
        reslist.add(new ArrayList<Integer>());
        
        for (int n : nums) {
            int size = reslist.size();
            for (int i = 0; i < size; i++) {
                List<Integer> sublist = new ArrayList<>(reslist.get(i));
                sublist.add(n);
                reslist.add(sublist);
            }
        }
        
        return reslist;
    }
}