https://leetcode.cn/problems/permutations/description/

<aside> 💡

排列问题与组合问题的差别：

• 排列问题不需要startIndex，而是每次都从第一个元素开始选取
• 相对的，一次排列中已经使用过的元素在之后的排列过程中不可再次被选中。 </aside>

明白了排列问题的特点，问题就变为如何知道哪些元素已经被使用过了。其解法也比较容易想到了：使用used数组标记使用过的元素

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

void backtracking(vector<int>& nums) {
    if (cur.size() == nums.size()) {
        ans.push_back(cur);
    }
    
    for (int i = 0; i < nums.size(); ++i) {
        if (used[i]) {
            continue;
        }
        used[i] = true;
        cur.push_back(nums[i]);
        backtracking(nums);
        cur.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
		// 使用used数组来标记使用过的元素，初始全为false
    used = vector<bool>(nums.size(), false);
    backtracking(nums);
    return ans;
}