Permutations II medium

Problem Statement

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

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

Steps

1. Sort the input array: Sorting the input array simplifies the process of identifying and avoiding duplicate permutations.

2. Backtracking: Utilize backtracking to generate all possible permutations. We'll maintain a vector currentPermutation to track the permutation being built and a boolean vector used to track which numbers have already been included in the current permutation.

3. Base Case: When the size of currentPermutation equals the size of the input array, a complete permutation has been formed. Add it to the result vector.

4. Recursive Step: Iterate through the input array. For each element:

   • If the element hasn't been used and (it's the first occurrence of this element or the previous occurrence of this element was already used), add it to currentPermutation, mark it as used, and recursively call the function.
   • After the recursive call, backtrack: remove the element from currentPermutation and mark it as unused. This allows exploration of other possibilities.

Explanation

The key to handling duplicates efficiently is the condition (i == 0 || nums[i] != nums[i - 1] || used[i - 1]). This ensures that we only consider an element if it's either the first element, or it's different from the previous element, or the previous element was already used in the current permutation. This prevents generating duplicate permutations.

The sorting step ensures that identical numbers are grouped together, making the comparison nums[i] != nums[i - 1] effective in skipping duplicate permutations.

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> currentPermutation;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end()); // Sort for efficient duplicate handling
        backtrack(nums, used, currentPermutation, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& currentPermutation, vector<vector<int>>& result) {
        if (currentPermutation.size() == nums.size()) {
            result.push_back(currentPermutation);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (!used[i] && (i == 0 || nums[i] != nums[i - 1] || used[i - 1])) {
                used[i] = true;
                currentPermutation.push_back(nums[i]);
                backtrack(nums, used, currentPermutation, result);
                currentPermutation.pop_back();
                used[i] = false;
            }
        }
    }
};

int main() {
    Solution solution;
    vector<int> nums1 = {1, 1, 2};
    vector<vector<int>> result1 = solution.permuteUnique(nums1);
    for (const auto& permutation : result1) {
        for (int num : permutation) {
            cout << num << " ";
        }
        cout << endl;
    }

    vector<int> nums2 = {1,2,3};
    vector<vector<int>> result2 = solution.permuteUnique(nums2);
     for (const auto& permutation : result2) {
        for (int num : permutation) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

Complexity

• Time Complexity: O(N * N!), where N is the number of elements in the input array. This is because there are N! permutations, and for each permutation, we perform O(N) operations (adding and removing elements).
• Space Complexity: O(N) for the recursive call stack and the currentPermutation vector. The space used by the result vector is O(N * N!), but this is not considered in the usual space complexity analysis for backtracking algorithms.