Permutations II Problem: Given a collection of numbers, nums
, that might contain duplicates, return all possible unique permutations in any order.
Example :
Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]]
Table of Contents
Permutations II Problem Solution
Problem Solution In Python
class Solution:
def permuteUnique(self, nums):
nums.sort()
result = []
self.permutation(nums, [],result)
return result
def permutation(self, numbers, curr, result):
if len(numbers) == 0:
result.append(curr)
for i in range(len(numbers)):
if i > 0 and numbers[i] == numbers[i-1]:
continue
self.permutation(numbers[0:i]+numbers[i+1:], curr + [numbers[i]], result)
Problem Solution In Java
public class Solution {
public List<List<Integer>> permute(List<Integer> nums) {
List<List<Integer>> lst = new ArrayList<List<Integer>>();
for(int i=0; i<nums.size(); i++) {
List<Integer> newNums = (List<Integer>)((ArrayList)nums).clone();
newNums.remove(i);
List<List<Integer>> subLst = permute(newNums);
if(subLst.isEmpty()) {
List<Integer> l = new ArrayList<Integer>();
l.add(nums.get(i));
lst.add(l);
} else {
for(List<Integer> l : subLst) {
l.add(nums.get(i));
lst.add(l);
}
}
while(i<nums.size()-1 && nums.get(i+1).equals(nums.get(i))) i++;
}
return lst;
}
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<Integer> numsLst = new ArrayList<Integer>();
for(int i : nums)
numsLst.add(i);
return permute(numsLst);
}
}
Problem Solution In C++
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> reval;
std::sort(nums.begin(),nums.end());
reval.push_back(nums);
while(nextPermutation(nums)){
reval.push_back(nums);
}
return reval;
}
private:
bool nextPermutation(vector<int>& nums){
int vio_index(nums.size()-2);
while(vio_index>=0 && nums[vio_index] >= nums[vio_index+1]){
-- vio_index;
}
if(vio_index == -1) return false;
std::reverse(nums.begin()+vio_index+1, nums.end());
//find the upper bound value
auto iter = std::upper_bound(nums.begin()+vio_index+1,nums.end(),nums[vio_index]);
std::swap(nums[vio_index],*iter);
return true;
}
};
Problem Solution In C
int** permuteUnique(int* nums, int numsSize, int* returnSize);
int** permute(int* nums, int numsSize, int* returnSize);
int cmpInt(const void * a, const void * b);
int factorial(int n);
int* removeIndex(int* nums, int n, int i);
int** permuteUnique(int* nums, int numsSize, int* returnSize)
{
qsort(nums, numsSize, sizeof(int), cmpInt);
return permute(nums, numsSize, returnSize);
}
int** permute(int* nums, int numsSize, int* returnSize)
{
int** res;
if (numsSize == 1) {
*returnSize = 1;
res = malloc(sizeof(int*));
res[0] = malloc(sizeof(int));
res[0][0] = nums[0];
} else {
*returnSize = 0;
res = malloc(sizeof(int*) * factorial(numsSize));
int i, j;
for (i = 0; i < numsSize; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip repeated number
int* sub = removeIndex(nums, numsSize, i);
int subSize;
int** subPermute = permute(sub, numsSize - 1, &subSize);
for (j = 0; j < subSize; j++, (*returnSize)++) {
res[*returnSize] = malloc(sizeof(int) * numsSize);
res[*returnSize][0] = nums[i];
memcpy(res[*returnSize] + 1, subPermute[j], sizeof(int) * (numsSize - 1));
free(subPermute[j]);
}
free(sub);
free(subPermute);
}
}
return res;
}
int cmpInt(const void * a, const void * b)
{
return (*(int*)a - *(int*)b);
}
int factorial(int n)
{
int i = 1;
while (n > 1) i *= n--;
return i;
}
int* removeIndex(int* nums, int n, int i)
{
int* res = malloc(sizeof(int) * (n - 1));
memcpy(res, nums, sizeof(int) * i);
memcpy(res + i, nums + i + 1, sizeof(int) * (n - i - 1));
return res;
}