# Unique Subsets ### Source - leetcode: [Subsets II | LeetCode OJ](https://leetcode.com/problems/subsets-ii/) - lintcode: [(18) Unique Subsets](http://www.lintcode.com/en/problem/unique-subsets/) ### Problem Given a list of numbers that may has duplicate numbers, return all possible subsets. #### Example If ***S*** = `[1,2,2]`, a solution is: ~~~ [ [2], [1], [1,2,2], [2,2], [1,2], [] ] ~~~ #### Note Each element in a subset must be in **non-descending **order.The ordering between two subsets is free.The solution set must not contain duplicate subsets. ### 題解 此題在上一題的基礎上加了有重復元素的情況，因此需要對回溯函數進行一定的剪枝，對于排列組合的模板程序，剪枝通常可以從兩個地方出發，一是在返回結果`result.add`之前進行剪枝，另一個則是在`list.add`處剪枝，具體使用哪一種需要視情況而定，哪種簡單就選誰。 由于此題所給數組不一定有序，故首先需要排序。有重復元素對最終結果的影響在于重復元素最多只能出現`n`次(重復個數為n時)。具體分析過程如下(此分析過程改編自 [九章算法](http://www.jiuzhang.com))。 以 [1,21,22][1, 2_1, 2_2][1,21,22] 為例，若不考慮重復，組合有 [],[1],[1,21],[1,21,22],[1,22],[21],[21,22],[22][], [1], [1, 2_1], [1, 2_1, 2_2], [1, 2_2], [2_1], [2_1, 2_2], [2_2][],[1],[1,21],[1,21,22],[1,22],[21],[21,22],[22]. 其中重復的有 [1,22],[22][1, 2_2], [2_2][1,22],[22]. 從中我們可以看出只能從重復元素的第一個持續往下添加到列表中，而不能取第二個或之后的重復元素。參考上一題Subsets的模板，能代表「重復元素的第一個」即為 for 循環中的`pos`變量，`i == pos`時，`i`處所代表的變量即為某一層遍歷中得「第一個元素」，因此去重時只需判斷`i != pos && s[i] == s[i - 1]`(不是 i + 1, 可能索引越界，而i 不等于 pos 已經能保證 i >= 1). ### C++ ~~~ class Solution { public: /** * @param S: A set of numbers. * @return: A list of lists. All valid subsets. */ vector<vector<int> > subsetsWithDup(const vector<int> &S) { vector<vector<int> > result; if (S.empty()) { return result; } vector<int> list; vector<int> source(S); sort(source.begin(), source.end()); backtrack(result, list, source, 0); return result; } private: void backtrack(vector<vector<int> > &ret, vector<int> &list, vector<int> &s, int pos) { ret.push_back(list); for (int i = pos; i != s.size(); ++i) { if (i != pos && s[i] == s[i - 1]) { continue; } list.push_back(s[i]); backtrack(ret, list, s, i + 1); list.pop_back(); } } }; ~~~ ### Java ~~~ class Solution { /** * @param S: A set of numbers. * @return: A list of lists. All valid subsets. */ public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> S) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (S == null) return result; // Collections.sort(S); List<Integer> list = new ArrayList<Integer>(); dfs(S, 0, list, result); return result; } private void dfs(ArrayList<Integer> S, int pos, List<Integer> list, ArrayList<ArrayList<Integer>> result) { result.add(new ArrayList<Integer>(list)); for (int i = pos; i < S.size(); i++) { // exlude duplicate if (i != pos && S.get(i) == S.get(i - 1)) { continue; } list.add(S.get(i)); dfs(S, i + 1, list, result); list.remove(list.size() - 1); } } } ~~~ ### 源碼分析 相比前一道題多了去重的判斷。 ### 復雜度分析 和前一道題差不多，最壞情況下時間復雜度為 2n2^n2n. 空間復雜度為 O(n)O(n)O(n). ### Reference - [Subsets II | 九章算法](http://www.jiuzhang.com/solutions/subsets-ii/)