Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example:
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
这道题目回溯的思路和手机键盘不同，手机键盘问题中每个节点向下扩展的个数是固定的。这道题目随着不断向下扩展，可选的元素在变少。
以数组 [1, 2, 3] 的全排列为例。
先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列（注意：递归结构体现在这里）； 再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列； 最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。
- 每个结点表示求解全排列问题的不同阶段，这些阶段通过变量的「不同的值」体现，这些变量的不同的值，称之为「状态」；
- 使用深度优先遍历有「回头」的过程，在「回头」以后， 状态变量需要设置成为和先前一样 ，因此在回到上一层结点的过程中，需要撤销上一次的选择，这个操作称之为「状态重置」；
- 深度优先遍历，借助系统栈空间，保存所需要的状态变量，在编码中只需要注意遍历到相应的结点的时候，状态变量的值是正确的
- 首先是正确性，只有遍历状态空间，才能得到所有符合条件的解，这一点 BFS 和 DFS 其实都可以；
- 在深度优先遍历的时候，不同状态之间的切换很容易 ，可以再看一下上面有很多箭头的那张图，每两个状态之间的差别只有 1 处，因此回退非常方便，这样全局才能使用一份状态变量完成搜索；
- 如果使用广度优先遍历，从浅层转到深层，状态的变化就很大，此时我们不得不在每一个状态都新建变量去保存它，从性能来说是不划算的；
- 如果使用广度优先遍历就得使用队列，然后编写结点类。队列中需要存储每一步的状态信息，需要存储的数据很大，真正能用到的很少 。
- 使用深度优先遍历，直接使用了系统栈，系统栈帮助我们保存了每一个结点的状态信息。我们不用编写结点类，不必手动编写栈完成深度优先遍历。
回溯算法会应用「剪枝」技巧达到以加快搜索速度。有些时候，需要做一些预处理工作（例如排序）才能达到剪枝的目的。预处理工作虽然也消耗时间，但剪枝节约的时间更多； 由于回溯问题本身时间复杂度就很高，所以能用空间换时间就尽量使用空间。
做题的时候，建议先画树形图 ，画图能帮助我们想清楚递归结构，想清楚如何剪枝。
在画图的过程中思考清楚：
-
分支如何产生；
-
题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？
-
哪些搜索会产生不需要的解？
如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？
c++
class Solution {
private:
vector<int> ans;
vector<vector<int>> ans_list;
public:
void backtrack(vector<int>& nums){
if (nums.empty()){
ans_list.push_back(ans);
return;
}
for (int i = 0; i < nums.size(); i++){
ans.push_back(nums[i]);
vector<int> newlist = nums;
newlist.erase(newlist.begin() + i);
backtrack(newlist);
ans.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
backtrack(nums);
return ans_list;
}
};执行用时：8 ms, 在所有 C++ 提交中击败了49.28%的用户
内存消耗：8.5 MB, 在所有 C++ 提交中击败了15.03%的用户
Attention
-
回溯问题也要分析其子结构，递归调用解决的同一类问题，只是尺寸不同
-
能用指针就用指针传值，速度快