Subset

[A general backtracking template](https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)

78 Subset

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

• Time O(2^n)

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    dfs(nums, 0, new ArrayList<>(), result);
    return result;
}

private void dfs(int[] nums, int index, List<Integer> subset, List<List<Integer>> result){
    result.add(new ArrayList(subset));
    for(int i = index; i < nums.length; i++){
        subset.add(nums[i]);
        dfs(nums, i + 1, subset, result);
        subset.remove(subset.size()-1);
    } 
}

90 Subset ll

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set)duplicate number in list

• Add duplicate condition

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    subsetsHelper(nums, new ArrayList(), 0, result);
    return result;
}

private void subsetsHelper(int[] nums,
                            ArrayList<Integer> subset,
                            int index,
                            ArrayList<ArrayList<Integer>> result){

    result.add(new ArrayList(subset));
    for(int i = index; i < nums.length; i++){
        if(i > index && nums[i] == nums[i-1]){ // 只使用第一個duplicate
            continue;    
        }
        subset.add(nums[i]);
        subsetsHelper(nums, subset, i + 1, result); //不是index+1
        subset.remove(subset.size()-1);
    }
}