题目：
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].
代码：
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > ret;
vector<int> none;
ret.push_back(none);
for ( size_t i = ; i < nums.size(); ++i ){
vector<vector<int> > tmp = ret;
ret.clear();
for ( size_t j = ; j < tmp.size(); ++j ){
for ( size_t k = ; k < i+; ++k ){
vector<int> ori = tmp[j];
ori.insert(ori.begin()+k, nums[i]);
ret.push_back(ori);
}
}
}
return ret;
}
};
tips：
参考（http://bangbingsyb.blogspot.sg/2014/11/leetcode-permutations-i-ii.html）
采用增量构造法（暴力法解决）：每次新增一个元素，对上次已有的permutations，从0到size挨个位置插入一遍。
[] // 注意一开始要给ret一个空的vector<int> 这样才循环才能run起来
[]
[ 1],[1 ]
[ 2 1], [2 1], [2 1 ], [ 1 2 ], [1 2], [1 2 ]
=======================================
又写了一版DFS的代码，如下：
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > ret;
vector<int> tmp;
vector<bool> used(nums.size(), false);
Solution::perpermute(nums, ret, tmp, used);
return ret;
}
static void perpermute(
vector<int>& nums,
vector<vector<int> >& ret,
vector<int>& tmp,
vector<bool>& used )
{
if ( tmp.size()==nums.size() )
{
ret.push_back(tmp);
return;
}
for ( int i =; i < nums.size(); ++i )
{
if (used[i]) continue;
tmp.push_back(nums[i]);
used[i] = true;
Solution::perpermute(nums, ret, tmp, used);
tmp.pop_back();
used[i] = false;
}
}
};
tips：
tmp用于不断构造一个permutation，每一层代表permutation的一个位置，每层递归添加一个元素。
如果判断某个元素是否能被添加到tmp的后面呢？这里的办法是维护一个bool数组：每个位置判断nums对应位置上的元素是否被使用。
dfs终止条件，如果tmp的size已经为整个nums的size了，证明构造出来一个排列，可以返回
===================================================
第二次过这道题，先用暴力增量法写了一个。这个跟subset的方法类似，可以沿用这个套路。
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > ret;
vector<int> none;
ret.push_back(none);
for ( int i=; i<nums.size(); ++i )
{
vector<vector<int> > tmp = ret;
ret.clear();
for ( int j=; j<tmp.size(); ++j )
{
for ( int k=; k<tmp[j].size(); ++k )
{
vector<int> curr = tmp[j];
curr.insert(curr.begin()+k, nums[i]);
ret.push_back(curr);
}
vector<int> curr = tmp[j];
curr.insert(curr.end(), nums[i]);
ret.push_back(curr);
}
}
return ret;
}
};
再用dfs写一遍。
class Solution {
public:
vector<vector<int> > permute(vector<int>& nums)
{
vector<vector<int> > ret;
vector<int> tmp;
vector<bool> used(nums.size(), false);
Solution::dfs(ret, nums, used, tmp);
return ret;
}
static void dfs(
vector<vector<int> >& ret,
vector<int>& nums,
vector<bool>& used,
vector<int>& tmp)
{
if ( tmp.size()==nums.size() )
{
ret.push_back(tmp);
return;
}
for ( int i=; i<nums.size(); ++i )
{
if (used[i]) continue;
tmp.push_back(nums[i]);
used[i] = !used[i];
Solution::dfs(ret, nums, used, tmp);
tmp.pop_back();
used[i] = !used[i];
}
}
};