力扣46题 全排列

题型属于回溯算法

1.递归函数参数

排列有序，因此需要一个used数组，标记已经选择的元素

2.递归终止条件

当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示达到了叶子节点。

3.单层搜索的逻辑

与组合问题相比最大的不同就是for循环里不用startindex了，而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

class Solution {
public: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里已经收录的元素，直接跳过used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}vector<vector<int>> permute(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};

排列问题的不同：
1.每层都是从0开始搜索而不是startindex
2.需要used数组记录path里都放了哪些元素了