Permutations II Problem Solution

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

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;
}