C++: Permutations

Thought Process

To generate all permutations of a given array, we use backtracking. We start by building permutations one element at a time. If the current element is already in the temporary permutation, we skip it. Otherwise, we add it to the permutation and recursively continue the process. This ensures that we generate all possible permutations of the array. 

class Solution {
public:
    void backTrack(vector<vector<int>> &ans, vector<int> &tmp, vector<int> nums){

        if(tmp.size()==nums.size()){
            ans.push_back(tmp);
            return;
        }

        for(int i=0;i<nums.size();i++){

            // Basically, checking whether tmp contains the element or not.
            // If Element exists, then continue.
            if(find(tmp.begin(),tmp.end(),nums[i])!=tmp.end())
                continue;

            tmp.push_back(nums[i]);
            backTrack(ans,tmp,nums);
            tmp.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        
        vector<vector<int>> ans;
        vector<int> tmp;

        backTrack(ans,tmp,nums);

        return ans;
    }
};

Code Complexity

Time Complexity: O(n * n!)

The algorithm generates all permutations of the input array, resulting in n! permutations, and each permutation takes O(n) time to construct, where 'n' is the size of the input.

Space Complexity: O(n)

The recursion stack depth is proportional to the size of the input('n'), and the temporary vector stores intermediate results.

Code copied!