LeetCode 46 全排列 - 回溯解法
https://leetcode.cn/problems/permutations/description/
思路
和组合问题类似，但是这里是排列，组合是每回只能加后面的元素，而排列问题可以加之前的元素，组合问题设置一个 index 来标记从 index 到最后中选值，排列问题每次都是从全部元素中选值（去除已经选过的元素）。
需要标记那些已经用过了， 可以传参也可以设置全局变量，但要记得维护。
这里使用全局变量 use ，没用过的为0， 用过的为1
for(int i = 0; i<max;i++){
if(loc[i]没用过){
path.push(loc[i]);
use[i] = 1; //及时设置use
add_path()
use[i] = 0 //别忘了下一侧循环时，本层的i 应该是没用过的。
path.pop()
}
}
代码
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
vector<int> lco_number;
vector<int> loc_use;
void add_path(){
if(path.size()==lco_number.size()){
result.push_back(path);
return;
}
for(int i = 0;i<lco_number.size();i++){
if(loc_use[i]!=1){
path.push_back(lco_number[i]);
loc_use[i] = 1;
add_path();
path.pop_back();
loc_use[i] = 0;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
lco_number = nums;
vector<int> tmp(nums.size(),0);
loc_use = tmp;
add_path();
return result;
}
};