本文參考代碼隨想錄

給定一個 沒有重復 數字的序列，返回其所有可能的全排列。

示例:

輸入: [1,2,3]
輸出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路

排列是有序的，在排列問題中不需要startIndex；但排列問題需要一個used數組，標記已經選擇的元素

當收集元素的數組path的大小達到和nums數組一樣大的時候，說明找到了一個全排列，也表示到達了葉子節點，回溯終止。

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, vector<bool> used){if(path.size() == nums.size()){result.push_back(path);return;}for(int i = 0;i < nums.size(); i++){if(used[i] == true) continue;path.push_back(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.pop_back();}}
public:vector<vector<int>> permute(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};