Algorithm
Problem Name: 47. Permutations II
Problem Link: https://leetcode.com/problems/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;
}
Input
nums = [1,1,2]
Output
[[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>;
}
}
};
Input
nums = [1,2,3]
Output
[[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) {
result.add(new ArrayList<>(curr));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
continue;
}
curr.add(nums[i]);
visited[i] = true;
helper(nums, result, curr, visited);
curr.remove(curr.size() - 1);
visited[i] = false;
}
}
}
Input
nums = [1,1,2]
Output
[[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;
}
}
}
Input
nums = [1,2,3]
Output
[[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:
dic.add(p)
return list(dic)
Input
nums = [1,1,2]
Output
[[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>>();
result.Add(nums);
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;
result.Add(tempList);
}
}
}
return result;
}
}
}
Input
nums = [1,2,3]
Output
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]