Subsets

题目地址：
https://leetcode.com/problems/subsets/#/description

题目：

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:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路：
这道题就是用backtracking的方法就可以解决。然后这道题有follow up，如果有重复的数，可以先sort，然后判断是否和之前的数相等，如果一样，那么continue。

代码：

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> rst = new ArrayList<>();
    if(nums == null || nums.length == 0){
        return rst;
    }
    List<Integer> list = new ArrayList<>();
    helper(rst, list, nums, 0);
    return rst;
}

private void helper(List<List<Integer>> rst, List<Integer> list, int[] nums, int pos) {
    rst.add(new ArrayList<>(list));

    for(int i = pos; i <= nums.length - 1; i++){
        list.add(nums[i]);
        helper(rst, list, nums, i + 1);
        list.remove(list.size() - 1);
    }
}

Follow up：

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> rst = new ArrayList<>();
    if(nums == null || nums.length == 0){
        return rst;
    }
    Arrays.sort(nums);
    List<Integer> list = new ArrayList<>();
    helper(rst, list, nums, 0);
    return rst;
}

private void helper(List<List<Integer>> rst, List<Integer> list, int[] nums, int pos) {
    rst.add(new ArrayList<>(list));

    for(int i = pos; i <= nums.length - 1; i++){
        if(i != pos && nums[i - 1] == nums[i]){
            continue;
        }
        list.add(nums[i]);
        helper(rst, list, nums, i + 1);
        list.remove(list.size() - 1);
    }
}