90. Subsets II.md

90. Subsets II

Question

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

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Thinking:

• Method 1:回溯法
  • 还是类似普通subset的解法。
  • 通过一个HashMap装载当前出现过得数字（键），为了加入当前数字，添加的链表个数（值）
    • [], [1], 此时为了添加1所添加的链表的个数=>1,即未添加1之前的链表的个数(此时result中只有[])。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length == 0) return result;
        Arrays.sort(nums);
        backtrace(nums, nums.length - 1, new HashMap<Integer, Integer>(), result);
        return result;
    }
    private static void backtrace(int[] nums, int n, Map<Integer, Integer> used, List<List<Integer>> result){
        if(n == -1){
            result.add(new ArrayList<Integer>());
        }else{
            backtrace(nums, n - 1, used, result);
            int len = result.size();
            if(!used.containsKey(nums[n])){
                used.put(nums[n], len);
                for(int i = 0; i < len; i++){
                    List<Integer> temp = result.get(i);
                    List<Integer> temp1 = new ArrayList<>(temp);
                    temp1.add(nums[n]);
                    result.add(temp1);
                }
            }else{
                int time = used.get(nums[n]);
                for(int i = len - 1; i > len - 1 - time; i--){
                    List<Integer> temp = result.get(i);
                    List<Integer> add = new ArrayList<>(temp);
                    add.add(nums[n]);
                    result.add(add);
                }
            }
        }
    }
}

二刷

借鉴了一刷，需要用一个哈希表存储对于每一位的增加次数，就不会发生重复。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<>();
        if(nums.length == 0){
            return result;
        }
        backtrace(result, nums, nums.length - 1, new HashMap<Integer, Integer>());
        return result;
    }
    private void backtrace(List<List<Integer>> result, int[] nums, int index, Map<Integer, Integer> map){
        if(index == -1)
            result.add(new LinkedList<Integer>());
        else{
            backtrace(result, nums, index - 1, map);
            if(!map.containsKey(nums[index])){
                int size = result.size();
                map.put(nums[index], size);
                for(int i = 0; i < size; i++){
                    List<Integer> temp = new LinkedList<>(result.get(i));
                    temp.add(nums[index]);
                    result.add(temp);
                }
            }else{
                int count = map.get(nums[index]);
                List<List<Integer>> temp = new LinkedList<List<Integer>>();
                int size = result.size();
                for(int i = 0; i < count; i++){
                    List<Integer> l = new LinkedList<Integer>(result.get(size - 1 - i));
                    l.add(nums[index]);
                    temp.add(l);
                }
                result.addAll(temp);
            }
        }
    }
}

Third time

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if(nums.length == 0) return result;
        Arrays.sort(nums);
        dfs(result, nums, new LinkedList<Integer>(), 0);
        return result;
    }
    private void dfs(List<List<Integer>> result, int[] nums, List<Integer> temp, int index){
        result.add(new LinkedList<>(temp));
        for(int i = index; i < nums.length; i++){
            while(i > index && i < nums.length && nums[i] == nums[i - 1]) i++;
            if(i >= nums.length) break;
            temp.add(nums[i]);
            dfs(result, nums, temp, i + 1);
            temp.remove(temp.size() - 1);
        }
    }
}

C++ version

class Solution {
    vector<vector<int>> res_;
    void dfs(int cur, vector<int>& temp, vector<int>& nums){
        res_.emplace_back(temp);
        int size = nums.size();
        for(int i = cur; i < size; ++i){
            while(i > cur && i < size && nums[i] == nums[i - 1]) ++i;
            if(i >= size) break;
            temp.emplace_back(nums[i]);
            dfs(i + 1, temp, nums);
            temp.pop_back();
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> temp;
        dfs(0, temp, nums);
        return res_;
    }
};