# [Leetcode C++] Permutations

## Problem

Given a collection of distinct numbers, return all possible permutations.

For example,
`[1,2,3]` have the following permutations:

```[
[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;
}
}
};
```