给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1],
[3,1,2], [3,2,1] ]
这道题其实就是看你如何遍历这棵搜索树。
输入1,2,3情况下的求解树，如下：
那么可以使用DFS或者BFS来遍历这棵树。广度优先也是可以做的，我暂时还没尝试。
如果用DFS来做：
第一种思路，交换（可能比较难想到）
说白了每次挑一个数字出来，为了保证不重复，我就换就行了嘛。
void perm(int list[], int k, int m) { if (k == m) { for (int i = 0; i <= m; i++) { cout << list[i]; } cout << endl; } else { //处理所有结点，列举所有可能，注意递归的时候也会进入for循环, //这样就帮助你递归子问题所有可能。 for (int i = k; i <= m; i++) { swap(list[k], list[i]);//挑选一个数放到最前面 perm(list, k + 1, m);//排列当前数字后面的一个数 swap(list[k], list[i]);//回溯的时候恢复 } } }
第二种思路，设置标志（像转密码锁一样，但是我要每位保证数字都不同）
每次循环挑一个数，挑中我就置为true，挑不中我就接着遍历。
void perm2(bool used[],vector<int> &res, vector<int> &list) { if (res.size() == list.size()) { for (int i = 0; i <res.size(); i++) { cout << res[i]; } cout << endl; return; } else { for (int i = 0; i <list.size(); i++) { if (used[i] == false) { used[i] = true; res.push_back(list[i]); perm2(used, res, list); used[i] = false; res.pop_back(); } } } }
总结：像这种问题步骤，第一步我怎么列举这些数（怎么遍历这棵树，for循环），第二步终止条件是啥，第三步，怎么选点，第四步，怎么回溯。下面给个dfs模板，有了以上想法，直接修修改改就行了。
void DFS(int x,int y) { if(满足所需要的条件) { 相应的操作；return；} else{ for(int i= ; ;) //如果是方向的话，会枚举方向 { 枚举加方向的新坐标； if(界限 ：例如：不能出到地图外，有障碍，已经访问过) continue; 设置已经访问新坐标； DFS(新坐标); 恢复到未被访问； } } }
