Problem

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Analysis

We can use DFS approach, we maintain a temporary vector for current permutation
– then we traverse the array to add unused nums to the vector
– that means we need a vector to keep track which num has been used

Time complexity:
– T(n) = n*T(n-1) + 1, thus it is O(n!)
– reference: https://stackoverflow.com/questions/41627749/time-complexity-of-permutation-function

Solution

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> allPer;
        vector<int> currPer;
        //keep track of whether nums[i] has been used
        vector<bool> used(nums.size(), false);
        getAllPermute(nums, allPer, currPer, used);
        return allPer;
    }
    
    //recursively find all permutation
    void getAllPermute(vector<int>& nums, vector<vector<int>>& allPer, vector<int>& currPer, vector<bool>& used){
        if(currPer.size()==nums.size()){
            allPer.push_back(currPer);
            return;
        }
        
        for(int i=0; i<nums.size(); i++){
            //if nums[i] has already been used, skip
            if(used[i]) continue;
            
            //otherwise, add to the permutation, and recursively build the array
            currPer.push_back(nums[i]);
            used[i] = true;
            getAllPermute(nums, allPer, currPer, used);
            currPer.pop_back();
            used[i] = false;
        }
    }
};