Given a collection of 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], and [3,2,1].
思路：将元素一个一个的插入，首先只有一个元素{1}，此时，插入之后会的到两个vector<int>，{1,2}，{2,1}，然后继续插入第三个元素3，会得到{3,1,2}，{1,3,2}，{1,2,3}和{3,2,1}，{2,3,1}，{2,1,3}。
依次类推，将所有的元素插入其中。
C++代码实现：
#include<iostream> #include<vector> using namespace std; class Solution { public: vector<vector<int> > permute(vector<int> &num) { if(num.empty()) return vector<vector<int> >(); vector<vector<int> > ret{{num[0]}}; size_t i,j,k; for(i=1;i<num.size();i++) { vector<int> temp1; vector<vector<int> > temp2=ret; ret.clear(); for(j=0;j<temp2.size();j++) { temp1=temp2[j]; k=0; while((temp1.begin()+k)!=temp1.end()) { temp1.insert(temp1.begin()+k,num[i]); ret.push_back(temp1); temp1=temp2[j]; k++; } temp1.push_back(num[i]); ret.push_back(temp1); } } return ret; } }; int main() { Solution s; vector<int> vec={1,2,3,4}; vector<vector<int> > result=s.permute(vec); for(auto a:result) { for(auto v:a) cout<<v<<" "; cout<<endl; } }
运行结果：
原文：http://www.cnblogs.com/wuchanming/p/4112716.html