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

Related issue: 78 Subsets

backtracking, pruning, 回溯法， 剪枝。

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0) return res;
        List<Integer> cur = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums, res, 0, cur);
        return res;
    }

    private void dfs(int[] nums, List<List<Integer>> res, int start, List<Integer> cur){
    //you DONT check if start == nums.length; cause you need to collect every thing.
        res.add(new ArrayList<Integer>(cur));
        for(int i=start; i< nums.length; i++){
            if( i != start && nums[i] == nums[i-1]) continue;
            cur.add(nums[i]);
            dfs(nums, res, i+1, cur); 
            cur.remove(cur.size()-1);
        }
    }
}

if you check the size, then for [1,2,2,2], the result is empty.

         if(k == nums.length ){
            res.add(new ArrayList<Integer>(list));
            return;
        }