题目
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]示例 3：
输入：nums = [1]
输出：[[1]]提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
解答
- 回溯
用回溯法模拟全排列的过程。
定义一个递归函数backtrack(first, output)表示从左往右填到第first个位置，当前排列为output，所以有以下两种情况：
- 若
first = n，则说明n个位置已经填完了，找到了一个可行的解，此时需要把output放入答案数组中，递归结束。 - 如果
first < n，我们需要考虑在第first个位置上我们需要填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组vis来标记已经填过的数，如果有数未被标记，就尝试填入，并将其标记，然后继续调用backtrack(first + 1, output)，回溯时要撤销之前的标记以及已经填入的数字，但是标记数组增加了算法的空间复杂度。
我们将题目给定的n个数的数组nums划分为左右两个部分，左边为已经填过的数，右边是待填的数，在回溯时只需要动态维护这个数组即可。
具体的来说，如果我们已经填到第first个位置，那么nums数组中[0, first - 1]是已经填过的数的集合，[first, n - 1]是待填数的集合。我们肯定是用[first, n - 1]的数去填第first个数，假设待填的数的下标为i，那么填完以后我们将第i个数和第first个数交换，即能使得在第first+1个数的时候nums数组的[0, first]部分为已填过的数，[first + 1, n - 1]为待填的数，回溯的时候交换回来就可以完成撤销操作。
举个简单的例子，假设我们有 [2,5,8,9,10]这 5 个数要填入，已经填到第 3 个位置，已经填了 [8, 9] 两个数，那么这个数组目前为 [8, 9|2, 5, 10] 这样的状态，分隔符区分了左右两个部分。假设这个位置我们要填 10 这个数，为了维护数组，我们将 2 和 10 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填 [8, 9, 10|2, 5] 。C++实现如下：
class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len) {
//所有数都填完了
if (first == len) {
res.emplace_back(output);
//和push_back()类似，emplace_back() 用来给容器中添加元素。
//在容器尾部添加一个元素，调用构造函数原地构造，不需要触发拷贝构造和移动构造。因此比push_back()更加高效。
return;
}
for (int i = first; i < len; ++i) {
//动态维护数组
swap(output[i], output[first]); //swap用于交换两个int型变量的值
//继续递归填下一个数
backtrack(res, output, first + 1, len);
//撤销操作
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
};