# [LeetCode 90. Subsets II](https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/613/week-1-august-1st-august-7th/3837/)
### Daily challenge Aug 3, 2021 (MEDIAN)

>Given an integer array `nums` that may contain duplicates, return all possible subsets (the power set).
>
>The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

:::info
**Example 1:**
**Input:** nums = [1,2,2]
**Output:** [[],[1],[1,2],[1,2,2],[2],[2,2]]
:::

:::info
**Example 2:**
**Input:** nums = [0]
**Output:** [[],[0]]
:::

:::warning
**Constraints:**
* 1 <= nums.length <= 10
* -10 <= nums[i] <= 10
:::

---

### Approach 1 : Iterator :bulb: + :book:
**`4 ms ( 76.59% )`** **`O()`**

1. 將 `nums` 排序後，再依序找出他的 `subsets`。
2. 假設 **`index = i`** :
> * **`nums[index] != nums[index-1]`** :
---> 可以遍歷現有的 **`ans`**，再 `ans[j]` 後加上 `nums[index]`，就能得到新的 `subset`。
> * **`nums[index] == nums[index-1]`** :
---> 表示連續兩個數字相同，所以不能夠從 `ans[0]` 開始建立，因為會得到與 `index - 1` **重複**的答案。
---> 所以應該另外紀錄 **`size = ans.size()`**，表示 `index - 1` 所新建立的**開始位置**。
> * **`startIndex = 0`** ---> 不同數字。
**`startIndex = size`** ---> 連續相同數字。

---

:::warning
**為什麼要使用 `startIndex` ?**

Example : **`nums = [1, 2, 2]`**。
由 `[1, 2]` 建立出來的 **`ans = [[], [1], [2], [1,2]]`**。
接下來是 `[1, 2, 2]`
> * 不使用 :
> ---> **`ans = [[], [1], [2], [1,2], [2],　[1,2], [2,2], [1,2,2]]`**。
> ---> 可以發現 `[2]`、`[1,2]` 會重複出現。
> * 使用 ( **`startIndex = 2`** ) :
> ---> **`ans = [[], [1], [2], [1,2], [2,2], [1,2,2]]`**。
> ---> 正確　！！

可以發現遇到相同的數字時，如果我們再從頭開始建立的話，就會出現**重複**的答案，所以應該要跳過。
:::

// Iterator
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans(1);
        
        sort(nums.begin(), nums.end());
        
        int startIndex = 0, size = 1;
        for(int i=0; i<nums.size(); i++){
            startIndex = (i > 0 && nums[i] == nums[i-1]) ? size : 0;
            size = ans.size();
            for(int j=startIndex; j<size; j++){
                vector<int> temp = ans[j];
                temp.push_back(nums[i])  ;  
                ans.push_back(temp);    
            }
        }
        
        return ans;
    }
};

### Approach 2 : Recursion ( Backtracking ) :book:
**`4 ms ( 76.59% )`** **`O()`**

與 **`Approach 1`** 概念相同，如果重複就不用計算。
作法類似 `DFS`。

:::warning

    backtracking(nums, current, ans, i+1);

`startIndex = i + 1`。
:::

:::success
**`nums = [1,2,2]`**、**`ans = [[]]`**。
* **`startIndex = 0`** ，`(#) 表示 startIndex`。
i=0 ---> `[1]` -> `[1,2]` (1) -> `[1,2,2]` (2) -> ~~`[1,2]` -> `[1]` -> `[]`~~。
i=1 ---> `[2]` -> `[2,2]` (2) -> ~~`[2]` -> `[]`~~。
i=2 ---> `[2]` :x: ( **`nums[index] == nums[index-1]`** )。
* **`ans = [[], [1], [1,2], [1,2,2], [2], [2,2]]`**。
:::

// recursion
class Solution {
public:
    void backtracking(vector<int>& nums, vector<int>& current, vector<vector<int>>& ans, int startIndex){
        ans.push_back(current);
        
        for(int i=startIndex; i<nums.size(); i++){
            if(i == startIndex || nums[i] != nums[i-1]){
                current.push_back(nums[i]);
                backtracking(nums, current, ans, i+1);
                current.pop_back();
            }
        }
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> current;
        vector<vector<int>> ans;
        
        backtracking(nums, current, ans, 0);
        return ans;
    }
};