全排列

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].

题目意思：

给定一个集合，求全排列。

解题思路：

一般的话，有两种思路可以考虑。递归和DFS遍历树。

这里我只用了递归的方法，关于怎么建一棵树然后DFS，可以参考 这里。

这对于练习对递归的理解真是个不错的题目。

以[1,2,3]举例，可以用纸笔画一画，分别以1,2,3为根，画出三棵树来，然后由根到每一个节点就对应着一个排列。

首先最外层肯定要有一个for循环来一次遍历这里面的元素决定出根节点，然后在循环中递归。

其中，有两点需要注意的：

要设置一个bool型的visited数组，大小和num一样大，来标记num中对应的元素是否已经访问过了，对于还没有访问过的，我们才可以把它加到element里来。这样可以避免在树的不同层出现同一个数。
在element已经完成了一次排列后，对element进行pop_back()，然后将pop出来的数对应的visited设置为true，表示它现在可以被访问了。举例来说，当element中已经有了[1,2,3]并且添加到result里后，进行一个pop_back()剩下[1,2]并将visited[2]置为true，然后跳到上一层调用，再pop_back()剩下[1]并将visited[1]置为true，此时for循环i++，此时visited[2]为true，即向element里添加num[2]，element变成[1,3]，接着再调用递归，在下一层因为visited[0]为false，visited[1]为true，element将添加num[1]变成[1,3,2]。

对递归不熟的朋友，可以一边对着代码，一边用笔画一下几个树，过几遍就OK拉！

代码如下：

 1 #include <vector>
 2 #include <iostream>
 3 using namespace std;
 4 
 5 class Solution {
 6 public:
 7     vector<vector<int> > permute(vector<int> &num) {
 8         vector<vector<int>> result;
 9         vector<int> element;
10 
11         int len = num.size();
12         bool *visited = new bool[len];
13         memset(visited,false,len);
14 
15         helper(num,result,element,visited);
16         return result;
17     }
18 
19 private:
20     void helper(vector<int> &num,vector<vector<int>> &result,vector<int> &element,bool *visited){
21         if(element.size() == num.size()){
22             //element中元素和num中元素一样多，说明得到了一个全排列，放进result里
23             result.push_back(element);
24             return ;
25         }
26 
27         for(int i = 0; i < num.size(); i++){
28             if(!visited[i]){
29                 visited[i] = true;
30                 element.push_back(num[i]);
31                 helper(num,result,element,visited);
32 
33                 element.pop_back();
34                 visited[i] = false;
35             }
36         }
37     }
38 };
39 
40 int main(){
41     Solution s;
42     vector<int> num;
43     num.push_back(1);
44     num.push_back(2);
45     num.push_back(3);
46     s.permute(num);
47 }