# LC 47. Permutations II

### [Problem link](https://leetcode.com/problems/permutations-ii/)

###### tags: `leedcode` `medium` `c++` `Backtracking`

Given a collection of numbers, <code>nums</code>,that might contain duplicates, return all possible unique permutations **in any order** .

**Example 1:**

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

**Example 2:**

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

**Constraints:**

- <code>1 <= nums.length <= 8</code>
- <code>-10 <= nums[i] <= 10</code>

## Solution 1
#### C++

class Solution {
public:
    vector<vector<int>> res;

    void backtracking(vector<int> &nums, vector<int> &path, vector<bool> &isUse) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i - 1] == nums[i] && isUse[i - 1] == false) {
                continue;
            }
            if (isUse[i] == true) {
                continue;
            }
            isUse[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, path, isUse);
            path.pop_back();
            isUse[i] = false;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> path;
        vector<bool> isUse(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtracking(nums, path, isUse);
        return res;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n * n!) | O(n) |

## Note
[代碼隨想錄](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0047.%E5%85%A8%E6%8E%92%E5%88%97II.md)

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

這段code中used[i - 1] == false這部分依然不太懂, 以後再回來看