Leetcode/F家，亚马家--78. Subsets I/90.II (Back Tracking)

78. Subsets I（Back Tracking）

• Difficulty: Medium

https://leetcode.com/problems/subsets/

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],
  []
]

Company: Amazon Uber Facebook

思路：用dfs, add path to result every time, remove last char of path once reach end point.
关键字： Back Tracking

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

90. Subsets II-- with duplicates （Back Tracking）

• Difficulty: Medium

https://leetcode.com/problems/subsets-ii/

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

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

Company: Facebook

思路：Need array to be sorted for skiping duplicated elements. 
          用dfs, add path to result every time, skip element when there is duplicate
          remove last char of path once reach end point.
关键字： Back Tracking

public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);//need to be sorted to track duplicated elements
        dfs(res,0,nums,new ArrayList<Integer>());
        return res;
    }
    public void dfs(List<List<Integer>> res,int index,int[] nums,List<Integer> path){
        res.add(new ArrayList<Integer>(path));
        for(int i=index;i<nums.length;i++){
            if(i>index&&nums[i-1]==nums[i])continue;
               //Skip duplicates: eg: [1,2,2] will get second [1,2(index=2 bc return from[1,2,2]),i=3)],skip 2nd 2.
            path.add(nums[i]);
            dfs(res,i+1,nums,path);
            path.remove(path.size()-1);
        }
    }
}