Daily Dose of DSA - Day 16

Question Link : https://leetcode.com/problems/permutations/description/

Recursive Method:

The permutations function is a recursive helper function that generates permutations. It takes three parameters: id to keep track of the current index, v which represents the vector containing the current permutation, and s which is a set to store unique permutations.

Here's a step-by-step breakdown of the code:

1. The permutations function starts by calculating the size of the vector v and checks if id is greater than or equal to n (the size of v). If id is greater than or equal to n, it means all elements have been fixed in their positions, and we have a complete permutation. In this case, the current permutation v is inserted into the set s to store unique permutations, and the function returns.

2. If id is less than n, the function enters a loop starting from j = id to n - 1. This loop iterates over the remaining elements of the vector, considering each element as the first element in the permutation.

3. Within the loop, the elements at indices j and id are swapped using the swap function. This swaps the current element with the element at id, fixing it in its position for the current permutation.

4. The permutations function is recursively called with id + 1 to generate permutations for the remaining elements. This recursive call handles the generation of all possible permutations by fixing the current element and recursively permuting the remaining elements.

5. After the recursive call, the swapped elements are restored to their original positions by swapping v[j] and v[id] again. This is necessary to backtrack and explore other possibilities for permutations.

6. The loop continues, considering the next element as the first element and repeating the process to generate all permutations.

7. Once the loop completes, the permutations function ends, and we have generated all unique permutations of nums using recursion.

8. The permute function serves as a wrapper function that initializes the vector v and the set s. It calls the permutations function with an initial id of 0 to start generating permutations. After generating all permutations, the unique permutations stored in the set s are copied to a vector v and returned as the final result.

In summary, the code recursively generates all possible permutations of a given vector nums by swapping elements and backtracking. The use of a set ensures that only unique permutations are stored. The final result is a vector of all unique permutations.

class Solution {
public:

   void permutations(int id,vector<int> &v ,set<vector<int>> &s)
   {
       int n = (int)v.size();
       if(id>=n) 
       {
           s.insert(v);
           return ;
       }

       for(int j = id ; j<=n-1;j++)
       {
           swap(v[j],v[id]);
           permutations(id+1,v,s);
           swap(v[j],v[id]); //backtrack
       }

       return ;
   }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> v;
        set<vector<int>> s;
        permutations(0,nums,s);
        for(auto it:s)
        {
            v.push_back(it);
        }

        return v;

    }
};

The space complexity of the set s used to store permutations is indeed O(n * n!).

In the worst case, there can be n! permutations of the input vector nums, and each permutation has a length of n. Storing all these permutations in the set s will require O(n * n!) space.

Therefore, the correct space complexity of the provided code is O(n * n!) due to the space required to store the permutations in the set s.

Iterative Method:

In this iterative solution, we start with the initial permutation and then generate new permutations by inserting the next number at different positions in each existing permutation. We iterate through all possible positions to split the vector and generate new permutations accordingly. The process continues until all possible permutations are generated.

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        result.push_back(nums); // Initial permutation

        int n = nums.size();

        // Iterate through all possible positions to split the vector
        for (int i = 0; i < n - 1; i++) {
            int size = result.size();

            // Generate new permutations by inserting the next number at         different positions
            for (int j = 0; j < size; j++) {
                for (int k = i + 1; k < n; k++) {
                    vector<int> perm = result[j];
                    swap(perm[i], perm[k]);
                    result.push_back(perm);
                }
            }
        }

        return result;
    }
};

The time complexity of the above iterative solution is O(n * n!), where n is the length of the input vector. This is because there are n! permutations of a vector of size n, and for each permutation, we iterate through n-1 positions to generate new permutations.

The space complexity of the above method is O(n n!), as we need to store all the generated permutations in the result vector*.* Since there are n! permutations and each permutation has n elements, the total space required is proportional to n n!.