題目描述
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].
題目大意
給定一個(gè)數(shù)組集合肤京，返回所有可能的排列胀莹。
思路
給的提示是分治+遞歸。
分治：就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題屉凯，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解与殃，原問(wèn)題的解即子問(wèn)題的解的合并单山。
由實(shí)例可以看出來(lái)，全排列是有規(guī)律可循的：
第一個(gè)排列是集合由小到大排列幅疼；
第二個(gè)交換了最后兩個(gè)數(shù)字米奸；
第三個(gè)交換了一二兩個(gè)數(shù)字；
第四個(gè)是在第三個(gè)的基礎(chǔ)上交換了二三兩個(gè)數(shù)字爽篷；
... ...
代碼
#include<iostream>
#include<vector>
using namespace std;
void permute_help(vector<vector<int> > &, vector<int> &, int);
vector<vector<int> > permute(vector<int> &num)
{
vector<vector<int> > res;
if(num.size() == 0)return res;
permute_help(res, num, 0);
return res;
}
void permute_help(vector<vector<int> > &res, vector<int> &num, int index)
{
if(index == num.size()-1)
{
res.push_back(num);
return;
}
for(int i=index; i<num.size(); i++)
{
swap(num[i], num[index]);
permute_help(res, num, index+1);
swap(num[i], num[index]);
}
}
int main()
{
vector<int> num;
for(int i=1; i<=3; i++)
{
num.push_back(i);
}
vector<vector<int> > res = permute(num);
for(int i=0; i<res.size(); i++)
{
for(int j=0; j<res[0].size(); j++)
{
cout << res[i][j]<<' ';
}
cout << endl;
}
return 0;
}
運(yùn)行結(jié)果
以上悴晰。
