47. Permutations II

📝 Problem Details

• Title: 47. Permutations II
• Link: https://leetcode.com/problems/permutations-ii/
• Difficulty: Medium
• Tags/Categories: Arrays Backtracking

input array nums can potentially contain duplicates return all possible unique permutations in any order

💭What Were My Initial Thoughts?

enumeration problem: searching for all possible permutations of a given list of integers
each permutation will be the same size 

- backtracking problem:
	- choice: picking which element to add next 
		- since we must use every number exactly once
		- duplicate numbers introduce the potential for choices to create repeated permutations

💡 Explanation of Solution

1. *Sort the input array

   • Sorting helps in handling duplicates by allowing us to check if a number has been used at the same recursion level.

2. *Use backtracking with a boolean used[] array

   • Maintain a boolean used[] array to track which elements are already included in the current permutation.

3. *Skip duplicate numbers

   • If nums[i] == nums[i - 1] and the previous occurrence nums[i - 1] hasn’t been used in the current recursion level, we skip nums[i] to avoid duplicate permutations.
   • This ensures that identical numbers are only considered in order, preventing repeated sequences.

Backtracking Steps: 4. If path.size() == nums.size(), we add path to the results.

5. Iterate through the sorted nums array:
   • If nums[i] is already used[i], skip it.
   • If nums[i] == nums[i - 1] and used[i - 1] == false, skip to avoid duplicates.
   • Otherwise:
     • Mark used[i] = true, add nums[i] to path, and recurse.
     • After recursion, remove nums[i] from path and reset used[i] = false (backtracking).

⌛ Complexity Analysis

Time Complexity: O(n!)
Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        vector<int> curr;
        vector<bool> visited(nums.size(), false);
 
        dfs(nums,visited,curr,result);
        return result;
    }
 
    void dfs(vector<int>& nums, vector<bool>& visited, vector<int>& curr, vector<vector<int>>& result) {
        if(curr.size() == nums.size()) {
            result.push_back(curr);
            return;
        }
 
        for(int i=0; i < nums.size(); i++) {
            if(visited[i]) continue; // skip used numbers
            if(i > 0 && nums[i] == nums[i-1] && !visited[i-1]) continue; // skip duplicates
 
            visited[i] = true;
            curr.push_back(nums[i]);
 
            dfs(nums,visited,curr,result);
            curr.pop_back(); // backtrack
            visited[i] = false; // backtrack and revoke decision
        }
    }
};