algoadvance

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

Example

Input: [1,1,2]
Output: [[1,1,2], [1,2,1], [2,1,1]]

Clarifying Questions

  1. Can the array be empty?
    • Yes, in which case the output should be an empty list.
  2. How are duplicates handled in the output?
    • All returned permutations must be unique.
  3. What is the maximum length of the array?
    • This isn’t explicitly stated, but typical constraints are such that brute force approaches are feasible.

Strategy

To generate unique permutations for an array that might contain duplicates, we can use the following strategy:

  1. Sort the Array: Start by sorting the array. Sorting helps in easily skipping duplicates.

  2. Use Backtracking with a Visited Array: Use a backtracking approach with a visited array to keep track of the elements that have been included in the current permutation.

  3. Skip Duplicates: During the recursive process, if we encounter the same element as the previous one and the previous one has not been used in the current recursion depth, we can skip it to avoid duplicate permutations.
    • This is fundamental in ensuring that we do not count the same set of elements in different orders as different permutations.
  4. Collect Results: Each time a complete permutation is formed (i.e., its length equals the original array), add it to the results list.

Code

Here’s the Python code to solve the problem:

def permuteUnique(nums):
    def backtrack(path, visited):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if visited[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
                continue
            visited[i] = True
            path.append(nums[i])
            backtrack(path, visited)
            path.pop()
            visited[i] = False

    nums.sort()
    result = []
    visited = [False] * len(nums)
    backtrack([], visited)
    return result

Explanation

  1. Sorting nums: The nums.sort() call sorts the input list to make it easier to handle duplicates.

  2. Backtracking Function: The backtrack function is used to generate permutations.
    • path is the current permutation being built.
    • visited is a list to keep track of which elements have been included in path.

  3. Base Case: If len(path) equals len(nums), append a copy of path to result.

  4. Iterating & Pruning: Iterate over nums using index i.
    • Skip the element if it’s already been added to path (checked using visited).
    • Skip duplicates: If nums[i] == nums[i - 1] and the previous element has not been used in this current state, skip it.
    • Otherwise, mark the element as visited, add it to path, and continue recursively.
    • Backtrack by removing the element from path and marking it as not visited.

Time Complexity

The time complexity is O(N * N!) where N is the length of the input list. This is because there are N! permutations and it takes O(N) time to copy each permutation to the result list.

Try our interview co-pilot at AlgoAdvance.com