给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

经典回溯问题。用一个 bool 数组标记每个数是否被使用

C++34 linesExpandCollapse
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> ans;
vector<int> path;
vector<bool> used;

void backtrack(vector<int>& nums) {
    if (path.size() == nums.size()) {
        ans.push_back(path);
        return;
    }
    
    // 枚举当前放哪个数字
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        
        path.push_back(nums[i]);
        used[i] = true;
        
        // 进入下一层
        backtrack(nums);
        
        // 撤销选择
        path.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    used.resize(nums.size(), false);
    backtrack(nums);
    return ans;
}