难度中等2447
给定一个不含重复数字的数组 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中的所有整数 互不相同
解题思路：回溯
排列问题和我们之前讲的组合问题不太一样，排列问题需要遍历所有的组合可能，包括顺序不同的组合可能，比如说 [1, 2] 和 [2, 1] 都需要满足，所以我们在排列问题中就不需要使用 index 来控制每次下一层也就是树枝之间的起始位置，只需要每次都从数组下标为 0 开始遍历所有可能即可！
但是这里还有一个问题，就是可能会出现重复调用了某个 nums[i]，比如说 [1, 2, 3] 中我们如果不对每个元素进行控制的话，可能会排列出 [1, 1, 1] 等情况，但是排列问题中我们只能让每个元素都出现一次，所以这里我们需要使用一个 used 数组进行判断：
- 将 used 数组初始化为 false
- 因为会出现重复的情况只在树枝之间，所以我们无需担心树层之间的重复，所以我们让 used[i] 为 false 表示是树层，而 used[i] 表示树枝，也就是我们在递归之前将 used[i] 变成 true，而回溯的时候将 used[i] 变成 false，这样子对下一个树层是没有影响的，只会对下一层的树枝产生影响！
- 而当我们判断到 used[i] == true，也就说明上一层树枝的这个元素已经遍历过了，所以我们直接 continue 即可！
class Solution {
public:
void backtracking(vector<int>& nums, vector<bool>& used)
{
if(v.size() == nums.size())
{
vv.push_back(v);
return;
}
for(int i = 0; i < nums.size(); ++i) // 每次都是从0开始遍历，和组合问题不一样，排列问题需要遍历所有可能
{
if(used[i] == true) // 只对树枝有影响，也就是现在使用了nums[i]，下一层就不能再使用nums[i]，防止重复！
continue;
v.push_back(nums[i]); // 处理
used[i] = true;
backtracking(nums, used); // 递归
used[i] = false; // 回溯
v.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return vv;
}
private:
vector<int> v;
vector<vector<int>> vv;
};