77全排列

全排列 题解1 回溯（经典思路）题解2 正向思路——可作模板 给定一个不含重复数字的数组 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 回溯（经典思路） class Solution { vector<vector<int>> ret; public: void backtrace(vector<int>& nums, int len){ if(len == nums.size()){ ret.push_back(nums); return; } for(int i = len; i < nums.size(); i++){ swap(nums[i], nums[len]); backtrace(nums, len+1); swap(nums[i], nums[len]); } } vector<vector<int>> permute(vector<int>& nums) { backtrace(nums, 0); return ret; } };

题解2 正向思路——可作模板 class Solution { vector<vector<int>> ret; public: void backtrace(vector<int>& nums, deque<int>& track, vector<bool>& used){ if(track.size() == nums.size()){ ret.push_back(vector<int>(track.begin(), track.end())); return; } for(int i = 0; i < nums.size(); i++){ // 用过就跳过 if(used[i]) continue; // 记录 used[i] = true; track.push_back(nums[i]); backtrace(nums, track, used); // 去掉 track.pop_back(); used[i] = false; } } vector<vector<int>> permute(vector<int>& nums) { // 双向queue deque<int> track; // 记录是否使用过（不需要len来记录加到哪了） vector<bool> used(nums.size(), false); backtrace(nums, track, used); return ret; } };