題目

給定一個不含重復數字的數組 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] <= 10
nums 中的所有整數 互不相同

分析

回溯算法框架:

路徑列表
void backtrack(選擇列表,路徑) {if 路徑 到達終點:路徑列表.add(路徑)returnfor 選擇 in 選擇列表:if 選擇 不合格:continue //進行下一個選擇路徑.add(選擇)backtrack(選擇列表,路徑)路徑.pop(選擇) //重新進行下一個選擇
}

C++代碼

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