## Algorithm

Problem Name: 47. Permutations II

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]]
```

Constraints:

• `1 <= nums.length <= 8`
• `-10 <= nums[i] <= 10`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
void bt(int **p, int *buff, int *v, int *nums, int sz, int l, int *n) {
int i;

if (l == sz) {
p[*n] = malloc(sz * sizeof(int));
//assert(p[k]);
memcpy(p[*n], buff, sz * sizeof(int));
(*n) ++;
return;
}
for (i = 0; i  <  sz; i ++) {
if (v[i] || (i > 0 && nums[i] == nums[i - 1] && !v[i - 1])) continue;
v[i] = 1;
buff[l] = nums[i];
bt(p, buff, v, nums, sz, l + 1, n);
v[i] = 0;
}
}
int cmp(const void *a, const void *b) {
int x = *(int *)a, y = *(int *)b;
return x  <  y ? -1 :
x > y ?  1 : 0;
}
int** permuteUnique(int* nums, int numsSize, int* returnSize) {
int *buff, **p, *v;
int i, n;
n = 1;
for (i = 2; i  < = numsSize; i ++) {
n = n * i;
}
p = malloc(n * sizeof(int *));
v = calloc(numsSize, sizeof(int));
buff = malloc(numsSize * sizeof(int));
//assert(p && v && buff);

qsort(nums, numsSize, sizeof(int), cmp);

n = 0;
bt(p, buff, v, nums, numsSize, 0, &n);
*returnSize = n;

free(buff); free(v);

return p;
}
``````
Copy The Code &

Input

cmd
nums = [1,1,2]

Output

cmd
[[1,1,2], [1,2,1], [2,1,1]]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector < vector<int>>res;
DFS(res, nums, 0);
return res;
}

void DFS(vector < vector<int>>& res, vector<int> nums, int pos){
if(pos == nums.size() - 1){
res.push_back(nums);
return;
}
for(int i = pos; i < nums.size(); i++){
if(i != pos && nums[i] == nums[pos]) continue;
swap(nums[pos], nums[i]);
DFS(res, nums, pos + 1>;
}
}
};
``````
Copy The Code &

Input

cmd
nums = [1,2,3]

Output

cmd
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List();
Arrays.sort(nums);
helper(nums, result, new ArrayList < >(), new boolean[nums.length]);
return result;
}

private void helper(int[] nums, List < List curr, boolean[] visited) {
if (curr.size() == nums.length) {
return;
}
for (int i = 0; i  <  nums.length; i++) {
if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
continue;
}
visited[i] = true;
helper(nums, result, curr, visited);
curr.remove(curr.size() - 1);
visited[i] = false;
}
}
}

``````
Copy The Code &

Input

cmd
nums = [1,1,2]

Output

cmd
[[1,1,2], [1,2,1], [2,1,1]]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const permuteUnique = function(nums) {
const result = [];
if (nums == null || nums.length === 0) {
return result;
}
const map = {};
for (let n of nums) {
map[n] = map.hasOwnProperty(n) ? map[n] + 1 : 1;
}
permuteUniqueHelper(map, nums.length, [], 0, result);
return result;
};

function permuteUniqueHelper(m, l, p, i, r) {
if (l === i) {
r.push(p.slice(0, l));
return;
}
for (let key of Object.keys(m)) {
if (m[key] > 0) {
m[key] = m[key] - 1;
p[i] = key;
permuteUniqueHelper(m, l, p, i + 1, r);
m[key] = m[key] + 1;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3]

Output

cmd
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def permuteUnique(self, nums):
dic = set()
for p in itertools.permutations(nums):
if p not in dic:
return list(dic)
``````
Copy The Code &

Input

cmd
nums = [1,1,2]

Output

cmd
[[1,1,2], [1,2,1], [2,1,1]]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _047_Permutations2
{
public IList < IList<int>> PermuteUnique(int[] nums)
{
var result = new List < IList<int>>();

int length = nums.Length;
int size, temp, i, j, k;
int[] tempArray;
IList < int> tempList;
for (i = 0; i  <  length; i++)
{
size = result.Count;
for (j = 0; j  <  size; j++)
{
tempArray = result[j].ToArray();
Array.Sort(tempArray, i, length - i);
result[j] = tempArray;
for (k = i + 1; k  <  length; k++)
{
tempList = new List<int>(result[j]);
if (tempList[k] == tempList[k - 1] ||
tempList[k] == tempList[i])
{ continue; }

temp = tempList[k];
tempList[k] = tempList[i];
tempList[i] = temp;
}
}
}

return result;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3]

Output

cmd
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]