90. 子集 II

題意：給你一個(gè)整數(shù)數(shù)組 nums ，其中可能包含重復(fù)元素，請(qǐng)你返回該數(shù)組所有可能的子集（冪集）。
解集 不能 包含重復(fù)的子集。返回的解集中，子集可以按 任意順序 排列

解題思路

解法1：
1.很經(jīng)典的回溯題型，給出的回溯算法模板：

void backtracking(參數(shù)) {
    if (終止條件) {
        存放結(jié)果;
        return;
    }

    for (選擇：本層集合中元素（樹(shù)中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) {
        處理節(jié)點(diǎn);
        backtracking(路徑，選擇列表); // 遞歸
        回溯，撤銷處理結(jié)果
    }
}

2.在注釋中，可以發(fā)現(xiàn)可以不寫(xiě)終止條件，因?yàn)楸緛?lái)我們就要遍歷整顆樹(shù)。有的同學(xué)可能擔(dān)心不寫(xiě)終止條件會(huì)不會(huì)無(wú)限遞歸？并不會(huì)，因?yàn)槊看芜f歸的下一層就是從i+1開(kāi)始的。
3.認(rèn)真審題，和上一題，明顯的不同是，含有重復(fù)元素，也就說(shuō)，子集很有可能重復(fù)
4.我們?cè)诿看渭尤隺ns之前，判斷子集是否已出現(xiàn)過(guò)，使用hashmap實(shí)現(xiàn)數(shù)據(jù)檢查

解題遇到的問(wèn)題

無(wú)

后續(xù)需要總結(jié)學(xué)習(xí)的知識(shí)點(diǎn)

本題理解還不深刻，歸根結(jié)底是對(duì)回溯算法不太了解，所以后續(xù)需要對(duì)回溯算法進(jìn)行深入學(xué)習(xí)、總結(jié)

##解法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;
    }
}