90. 子集 II

题意：给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列

解题思路

解法1：
1.很经典的回溯题型，给出的回溯算法模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

2.在注释中，可以发现可以不写终止条件，因为本来我们就要遍历整颗树。有的同学可能担心不写终止条件会不会无限递归？并不会，因为每次递归的下一层就是从i+1开始的。
3.认真审题，和上一题，明显的不同是，含有重复元素，也就说，子集很有可能重复
4.我们在每次加入ans之前，判断子集是否已出现过，使用hashmap实现数据检查

解题遇到的问题

无

后续需要总结学习的知识点

本题理解还不深刻，归根结底是对回溯算法不太了解，所以后续需要对回溯算法进行深入学习、总结

##解法1
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

class Solution {
    LinkedList<Integer> path = new LinkedList<Integer>();
    List<List<Integer>> ansList = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        dfs(0, nums);
        return ansList;
    }

    private void dfs(int i, int[] nums) {
        if (!isExist()) {
            ansList.add(new ArrayList<Integer>(path));
        }

        if (i >= nums.length) {
            return;
        }

        for (int j = i; j < nums.length; j++) {
            path.add(nums[j]);
            dfs(j + 1, nums);
            path.removeLast();
        }
    }

    private boolean isExist() {
        for (int j = 0; j < ansList.size(); j++) {
            List<Integer> list = ansList.get(j);
            if (list.size() == path.size()) {
                HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
                for (int i = 0; i < list.size(); i++) {
                    map.put(list.get(i), map.getOrDefault(list.get(i), 0) + 1);
                }

                for (int i = 0; i < path.size(); i++) {
                    if (map.containsKey(path.get(i))) {
                        if (map.get(path.get(i)) == 1) {
                            map.remove(path.get(i));
                        } else {
                            map.put(path.get(i), map.get(path.get(i)) - 1);
                        }
                    }
                }

                if (map.isEmpty()) {
                    return true;
                }
            }
        }
        return false;
    }
}