LeetCode46：全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

采用回溯法，最简单的是回溯的同时用一个数组标记哪些数已经用过，但是这样需要额外的空间。

可以直接把原数组分为两部分，前半部分为已经用过的数，后半部分为还没用的数，这样维护起来更加方便，也节省了空间。

 1 class Solution {
 2 public:
 3     vector<vector<int>> ret;
 4     vector<vector<int>> permute(vector<int>& nums) {
 5         backtrace(nums,0);
 6         return ret;
 7     }
 8 
 9     void backtrace(vector<int>& nums,int next){
10         if(next==nums.size()){
11             ret.push_back(nums);
12             return ;
13         }
14         for(int i=next;i<nums.size();i++){
15             swap(nums[i],nums[next]);
16             backtrace(nums,next+1);
17             swap(nums[i],nums[next]);
18         }
19 
20         return ;
21     }
22 };