---
title: Permutations
tags: 刷題筆記
---
### [47. Permutations II](https://leetcode.com/problems/permutations-ii/description/)
* 題目: Given a collection of numbers, nums, 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]]
* [參考](https://leetcode.com/problems/permutations-ii/solutions/933190/c-4-different-solutions-with-explanations-and-tips/): 解法三，先做排序，之後再遞迴的去找，swap 前如果遇到一樣的就跳過(記得做過 swap 後，nums[index] 的值會改變)

class Solution {
public:
    static inline void swap(int& a, int& b) 
    {
        int tmp = a;
        a = b;
        b = tmp;
    }

    void helper(vector<vector<int>>& ans, vector<int> nums, int index)
    {
        if (index == nums.size()-1) {
            ans.push_back(nums);
            return;
        }
        for (int i = index; i < nums.size(); ++i) {
            if (i != index && nums[i] == nums[index]) continue;      
            swap(nums[i], nums[index]);
            helper(ans, nums, index+1);
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        helper(ans, nums, 0);
        return ans;
    }
};