问题链接:46.permutations
依旧是用回溯法,与组合问题形成对比,组合问题每次只需要选i之后的数;排列则每次需要从0开始,但是不能重复,利用used[6] = {0}
这个used
数组来记录数是否已经进入path
,进入了path
就将used[i] = 1
,回溯时used[i] = 0
。
#include <vector>
using std::vector;
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
void track_back(vector<int> &nums, int index, int *used) {
if (path.size() >= nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == 1)
continue;
used[i] = 1;
path.push_back(nums[i]);
track_back(nums, i + 1, used);
path.pop_back();
used[i] = 0;
}
return;
}
public:
vector<vector<int>> permute(vector<int> &nums) {
int used[6] = {0};
track_back(nums, 0, used);
return res;
}
};
或者
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
int used[6] = {0};
void track_back(vector<int> &nums) {
if (path.size() >= nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == 1)
continue;
used[i] = 1;
path.push_back(nums[i]);
track_back(nums);
path.pop_back();
used[i] = 0;
}
return;
}
public:
vector<vector<int>> permute(vector<int> &nums) {
int used[6] = {0};
track_back(nums);
return res;
}
};
标签:vector,排列,nums,46,permutations,back,int,used,path
From: https://www.cnblogs.com/zwyyy456/p/16716769.html