We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Permutations II

Number: 47

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft, LinkedIn, TikTok, Meta

Problem Description

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Key Insights

  • Sort the input array to identify and easily skip duplicates.
  • Use backtracking to generate all candidate permutations.
  • Maintain a visited or used array to track elements already added to the current permutation.
  • When encountering a duplicate element, only use it if the previous identical element was used in the current recursion branch.
  • Backtrack by removing elements and resetting their used status when moving to another branch.

Space and Time Complexity

Time Complexity: O(n * n!) in the worst-case scenario, where n is the length of the input array. Space Complexity: O(n) for the recursion stack and used data structure, plus O(n * n!) to store the permutations.

Solution

The solution employs a backtracking algorithm. First, sort the nums array to ensure that duplicates are adjacent. Then, use a recursive function to build permutations by iterating through the array and choosing elements that have not been used yet. To handle duplicates, if the current element is the same as the previous one and the previous one was not used in the current recursive path, skip the current element. This ensures that duplicate permutations are never constructed. Data structures used include:

  • A list (or array) to hold the current permutation path.
  • A boolean visited (or used) array to keep track of whether a number is already in the current permutation.

After constructing a permutation of the same length as nums, add it to the results list, then backtrack to explore alternative possibilities.

Code Solutions

# Function to return all unique permutations of the input list nums.
def permuteUnique(nums):
    # Sort the numbers to facilitate duplicate checking.
    nums.sort()
    results = []
    permutation = []
    used = [False] * len(nums)
    
    # The helper function for backtracking.
    def backtrack():
        # If the current permutation is complete, add a copy to the results.
        if len(permutation) == len(nums):
            results.append(permutation.copy())
            return
        
        # Iterate over each number in nums.
        for i in range(len(nums)):
            # Skip used elements.
            if used[i]:
                continue
            # Skip duplicates: if the current element is the same as the previous and
            # the previous element was not used, then skip the current element.
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            # Mark the element as used.
            used[i] = True
            permutation.append(nums[i])
            # Recurse.
            backtrack()
            # Backtrack: unmark the element and remove it from the current permutation.
            used[i] = False
            permutation.pop()
    
    backtrack()
    return results

# Example usage:
# print(permuteUnique([1, 1, 2]))
← Back to All Questions