Last updated on March 7th, 2025 at 09:43 pm

Here, we see a Permutations II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Backtracking

Companies

Linkedin, Microsoft

Level of Question

Medium

Permutations II LeetCode Solution

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Backtracking”. Backtracking is a general algorithmic technique for solving problems incrementally, by trying partial solutions and then abandoning them if they are not suitable. In this case, the problem is to generate all unique permutations of a given list of numbers, and backtracking is used to explore all possible arrangements while avoiding duplicates.

3. Code Implementation in Different Languages

3.1 Permutations II 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;        
    }
};

3.2 Permutations II 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);
        }        
    }
}

3.3 Permutations II 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;    
};

3.4 Permutations II 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)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n! * n)	O(n!)
Java	O(n! * n)	O(n!)
JavaScript	O(n! * n)	O(n!)
Python	O(n! * n)	O(n!)

• The time complexity is dominated by the (O(n!)) term because the number of permutations grows factorially with the size of the input.
• The space complexity is dominated by the storage of the result, which contains (n!) permutations, each of length (n).
• The recursive implementations (Java, JavaScript, Python) also have an additional (O(n)) space overhead for the recursion stack.
• All implementations ensure uniqueness by either skipping duplicate numbers (JavaScript, Python) or leveraging sorted order (C++, Java).