My C++ Solution Share

• It is obvious that N numbers has N! permutations .

Here I assume an empty vector also has one permutation. It seems OJ didn't check the empty input case. Well, it doesn't matter.

``````class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
// Add an empty vector as the base case (empty input)
vector<vector<int> > permutations(1, vector<int>());
// Algrithm description:
//	Insert the current number in different spaces of previous permutations
for (vector<int>::size_type index = 0; index != num.size(); ++index)
{
vector<vector<int> > subPermutations(permutations);
permutations.clear();
for (vector<vector<int> >::size_type i = 0; i != subPermutations.size(); ++i)
{
for (int offset = 0; offset != subPermutations[i].size()+1; ++offset)
{
vector<int> temp(subPermutations[i]);
temp.insert(temp.begin() + offset, num[index]);
permutations.push_back(temp);
}
}
}
return permutations;
}
};
``````

• I think this wont work for (say) the test case {1,2,3,3}.

• Yes. The code cannot be applied to Permutation II when I encountered the problem. While it works for Permutation .

• here is my dp solution:

``````class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
int n = num.size();
if(!n) return vector<vector<int>>();
vector<vector<vector<int>>> dp(n);
dp[0] = vector<vector<int> >(1,vector<int>(1,num[0]));
for(int i = 1 ; i < n ; ++i){
for(int j = 0 ; j < dp[i-1].size() ; ++j){
dp[i-1][j].insert(dp[i-1][j].begin(),num[i]);
dp[i].push_back(dp[i-1][j]);
for(int k = 1 ; k < dp[i-1][j].size() ; ++k){
swap(dp[i-1][j][0],dp[i-1][j][k]);
dp[i].push_back(dp[i-1][j]);
swap(dp[i-1][j][0],dp[i-1][j][k]);
}
}
}
return dp[n-1];
}
};``````

• Like this non-recursive solution!

• The 'insert' operation is very time consuming. So the time complexity of this solution is N times more than that of the recursive solution.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.