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

Analysis:

DFS. The question can be translated to: for given num, find all non-duplicate combination with k elements. k = (1, nums.length)

So its a for loop for k, and each loop we call dfs to find out the answer for that k.

To avoid duplicate, we can sort the nums array, then use "nums[i] == nums[i-1] then skip" technique to skip duplicate elements being used at each level.

Complexity:

Time: ?

Space: ?

Code:

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> returnList = new ArrayList<List<Integer>>();
        returnList.add(new ArrayList<Integer>());
        if(nums == null || nums.length == 0){
            return returnList;
        }

        Arrays.sort(nums);

        for(int i = 1; i<= nums.length; i++){
            dfs(returnList, new ArrayList<Integer>(), i, 0, nums);
        }

        return returnList;
    }

    private void dfs(List<List<Integer>> returnList, List<Integer> tempList, int len, int pos, int[] nums){
        if(tempList.size() == len){
            returnList.add(new ArrayList<Integer>(tempList));
            return;
        }

        for(int i = pos; i < nums.length; i++){
            if(i > pos && nums[i] == nums[i-1]) continue;
            tempList.add(nums[i]);
            dfs(returnList, tempList, len, i+1, nums);
            tempList.remove(tempList.size() -1);
        }
    }
}