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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment