algoadvance

Leetcode 47. Permutations II

Problem Statement

The problem “Permutations II” from LeetCode requires generating all unique permutations of a given list of numbers that might contain duplicates. The result should not contain any duplicate permutations.

Example:

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

Clarifying Questions

1. Input Constraints: What is the length range of the input list?
   • The length can range from 0 to 8 (based on typical constraints for permutation problems).
2. Output Order: Does the order of the permutations in the output matter?
   • No, the order does not matter as long as all unique permutations are included.
3. Duplicate Permutation Handling: Should we assume the given input is sorted, or do we need to handle that in our algorithm?
   • We should handle sorting within the algorithm to manage duplicates effectively.

Strategy

1. Sorting: First, sort the input list to make it easier to skip duplicate elements when generating permutations.
2. Backtracking: Use a backtracking approach to generate all possible permutations.
3. Avoiding Duplicates: Use a visited array to keep track of used elements and avoid using the same element more than once at the same position in different recursive calls.

Steps:

1. Sort the Array: Helps in easily identifying and skipping duplicates.
2. Backtracking Function: Recursively build permutations while marking elements as used.
3. Visited Array: Keep track of which elements have been used at each position.

Code

Here is the C++ implementation:

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        std::vector<bool> visited(nums.size(), false);
        
        // Sort the nums array to handle duplicates
        std::sort(nums.begin(), nums.end());

        // Begin backtracking process
        backtrack(nums, current, visited, result);

        return result;
    }
    
private:
    void backtrack(std::vector<int>& nums, std::vector<int>& current, std::vector<bool>& visited, std::vector<std::vector<int>>& result) {
        // Base case: if current permutation is complete
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            // Skip used elements and duplicates
            if (visited[i] || (i > 0 && nums[i] == nums[i-1] && !visited[i-1])) {
                continue;
            }
            
            // Include this element in the current permutation
            visited[i] = true;
            current.push_back(nums[i]);
            
            // Recurse to build all possible permutations
            backtrack(nums, current, visited, result);
            
            // Backtrack: undo the choice
            current.pop_back();
            visited[i] = false;
        }
    }
};

Time Complexity

The time complexity of generating all unique permutations is determined by the number of permutations and the cost to generate each one. In the worst case:

• Sorting complexity: (O(n \log n))
• Permutations: The maximum possible unique permutations for n distinct elements are (n!). However, with duplicates, this number decreases, but the upper bound remains (n!).

Thus, the overall time complexity is (O(n \log n + n! \cdot n)):

• (n \log n) for the initial sorting.
• (n!) for generating all unique permutations.
• (n) for copying each permutation into the result list.

Therefore, the combined time complexity is effectively (O(n \cdot n!)) in the worst case.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?