Permutations II Leetcode Problem 47 [Python Solution]

I’m excited as we’re diving into the world of backtracking with the Permutations II Leetcode Problem, a follow-up to the first permutations problem.

If you’re new to this, don’t worry, we’ll guide you through it step by step.

Problem Overview

The task at hand is to generate all possible unique permutations of a given collection of numbers, which might contain duplicates.

These permutations should be returned in any order.

Let’s take a look at an example:

Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]

In this case, we have duplicates (two ones), and we need to ensure that we don’t end up with duplicate permutations.

This is where the challenge lies.

Understanding the Constraints

Before we dive into the solution, let’s understand the constraints of the problem:

• The length of the input array nums is between 1 and 8.
• The values in nums range from -10 to 10.

Problem Solution

We’ll approach this problem using backtracking.

But to avoid duplicates, we’ll make use of a clever data structure, a counter, from the collections module.

Here’s the Python code solution:

import collections

def permuteUnique(nums):
    result = []
    counter = collections.Counter(nums)

    def backtrack(perm, counter):
        if len(perm) == len(nums):
            result.append(perm.copy())

        for n in counter:
            if counter[n] == 0:
                continue
            perm.append(n)
            counter[n] -= 1
            backtrack(perm, counter)
            perm.pop()
            counter[n] += 1

    backtrack([], counter)

    return result

Now, let’s break this solution down step by step.

1. Bruteforce Approach

Our primary goal is to generate all unique permutations of the given input array, nums.

To achieve this, we use a counter to keep track of the count of each unique number in nums.

This is essential to prevent duplicates.

2. Backtracking

Our backtracking function, backtrack, is responsible for generating the permutations.

It follows this general outline:

1. Base Case: If the length of the current permutation perm is equal to the length of nums, we’ve found a complete unique permutation.

We add a copy of this permutation to the result.

2. Choice Exploration: We iterate through the unique numbers in counter.

If the count of a number is zero, we skip it.

Otherwise, we add that number to the perm, decrement its count in counter, and recursively call backtrack.

3. Undo the Choice: After the recursive call, we need to undo our choice to explore other possibilities.

We remove the number from perm, increment its count in counter, and continue the loop to explore other choices.

This backtracking approach ensures that we explore all possible permutations while avoiding duplicates.

Python Code Solution

Now, let’s provide the Python code for the solution in its entirety:

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    result = []
    counter = collections.Counter(nums)

    def backtrack(perm, counter):
        if len(perm) == len(nums):
            result.append(perm.copy())

        for n in counter:
            if counter[n] == 0:
                continue
            perm.append(n)
            counter[n] -= 1
            backtrack(perm, counter)
            perm.pop()
            counter[n] += 1

    backtrack([], counter)

    return result

This code efficiently generates all unique permutations of the given input array, nums, while handling duplicates gracefully.

Time and Space Complexity

Understanding the time and space complexity of our solution is crucial.

• Time Complexity: The time complexity of this solution is O(n * 2^n), where ‘n’ is the length of the input array nums.

This is because we generate all possible permutations.

In the worst case, there are n! (n factorial) unique permutations.

• Space Complexity: The space complexity is O(n) because we use the counter dictionary and the perm list, both of which can grow up to the size of the input array.

Reasoning Behind Our Approach

The core idea behind this approach is to use a counter dictionary to keep track of the count of each unique number in the input array.

This prevents us from making duplicate choices during permutation generation.

By backtracking through the decision tree of choices, we construct all unique permutations while maintaining the integrity of the original input array.

Related Interview Questions By Company:

• Ones And Zeroes LeetCode
• Design Circular Queue LeetCode
• Combinations LeetCode

Related Interview Questions By Difficulty:

• Palindrome Partitioning LeetCode
• Matchsticks To Square LeetCode
• Partition To K Equal Sum Subsets LeetCode

Related Interview Questions By Category:

• Sum Of Two Integers LeetCode
• Encode And Decode Tinyurl LeetCode
• Insert Interval LeetCode

Conclusion

In this guide, we explored the Permutations II problem, a LeetCode challenge that requires generating all possible unique permutations of an array containing potential duplicates.

We tackled this problem using backtracking and the collections.Counter data structure.

By carefully considering our choices and using backtracking to explore all possibilities, we achieved the goal of generating unique permutations.

Now that you understand the solution, you’re well-equipped to tackle similar problems and improve your algorithmic skills.

If you found this guide helpful, please consider liking and subscribing to support our our platform.

If you have any questions, suggestions, or just want to discuss coding, feel free to leave a comment below.

Question Link

Happy coding!