Permutations II LeetCode Solution

Here, We see Permutations II problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

Permutations II LeetCode Solution

Problem Statement ->

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

• C++ Solution
• Java Solution
• JavaScript Solution
• Python Solution

Permutations II Leetcode Solution C++ ->

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(begin(nums), end(nums));
		
        vector<vector<int>> output;
        output.emplace_back(nums);
        while (next_permutation(begin(nums), end(nums))) {
            output.emplace_back(nums);
        }
        return output;        
    }
};
Code language: C++ (cpp)

Permutations II Leetcode Solution Java ->

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (int n : nums) {
            countMap.put(n, countMap.getOrDefault(n, 0) + 1);
        }
        permuteUniqueHelper(result, nums.length, countMap, new ArrayList<>());
        return result;
    }

    private void permuteUniqueHelper(List<List<Integer>> result, int inputLength, HashMap<Integer, Integer> countMap, List<Integer> tempList) {
        if (tempList.size() == inputLength) {
            result.add(new ArrayList<>(tempList));
            return;
        }
        for (int num : countMap.keySet()) {
            int count = countMap.get(num);
            if (count == 0) {
                continue;
            }
            countMap.put(num, count - 1);
            tempList.add(num);
            permuteUniqueHelper(result, inputLength, countMap, tempList);
            tempList.remove(tempList.size() - 1);
            countMap.put(num, count);
        }        
    }
}
Code language: Java (java)

Permutations II Leetcode Solution JavaScript ->

var permuteUnique = function(nums) {
    const sorted = nums.sort((x,y) => x-y), permutations = [];
    const rcr = (arr, permutation) => {
        if (!arr.length) return permutations.push(permutation);
        let prev = -Infinity;
        for (let i = 0; i < arr.length; i++) {
            if (prev === arr[i]) continue;
            newArr = arr.slice(0, i).concat(arr.slice(i+1));
            rcr(newArr, [...permutation, arr[i]]);
            prev = arr[i];
        }
    }
    rcr(nums, []);
    return permutations;    
};
Code language: JavaScript (javascript)

Permutations II Leetcode Solution Python ->

class Solution(object):
    def permuteUnique(self, nums):
        res = []
        nums.sort()
        self.dfs(nums, [], res)
        return res
    
    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
        for i in xrange(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
Code language: Python (python)