LeetCode 46 全排列

题目：

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

示例:

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

解题思路：

递归求解，难点在于输出一个排列后怎么回溯。
记录当前序列的长度lever，当lever和nums长度相等时，即为一个排序out。
使用visited数字来标识某点是否被访问过。
以上的lever,out,visited都需要回溯。
回溯的方法是：在递归语句前设定某状态，在递归语句后取消该状态。

代码：

 1 class Solution {
 2 public:
 3     
 4     vector<vector<int>> permute(vector<int>& nums) {
 5         vector<vector<int>> ans;
 6         vector<int> out;
 7         vector<int> visited(nums.size(), 0);
 8         perDFS(nums,0,visited,out,ans);
 9         return ans;
10     }
11     
12     void perDFS(vector<int> nums, int lever, vector<int> &visited, vector<int> &out, vector<vector<int>> &ans) {
13         if(lever == nums.size()){
14             ans.push_back(out);
15             return ;
16         }
17         for(int i=0; i<nums.size(); ++i){
18             if(visited[i])
19                 continue;
20             visited[i] = 1;   //1、递归函数前设定visited和out 为某状态
21             out.push_back(nums[i]);
22             perDFS(nums,lever+1,visited,out,ans); //2、递归语句，lever在参数中回溯了
23             out.pop_back();   //3、递归函数后取消visited和out的某状态    
24             visited[i] = 0;
25         }
26     }
27 };