首页 > 代码库 > Permutations
Permutations
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; }}
运行结果：
Permutations
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。