## 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; } } };