Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

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

Solution

Time complexity: O(n!)

Space complexity: O(n + k)

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

vector<vector<int>> permuteUnique(vector<int>& nums) {

sort(begin(nums), end(nums));

vector<vector<int>> ans;

vector<int> used(nums.size());

vector<int> cur;

dfs(nums, cur, used, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, vector<int>& cur, vector<int>& used, vector<vector<int>>& ans) {

if (cur.size() == nums.size()) {

ans.push_back(cur);

return;

}

for (int i = 0; i < nums.size(); ++i) {

if (used[i]) continue;

// Same number can be only used once at each depth.

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

used[i] = 1;

cur.push_back(nums[i]);

dfs(nums, cur, used, ans);

cur.pop_back();

used[i] = 0;

}

};

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Paypal

Venmo
huahualeetcode

微信打赏