C++深度优先搜索全排列
时间: 2023-12-11 19:33:23 浏览: 40
以下是C++实现深度优先搜索全排列的代码示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void dfs(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& res) {
if (path.size() == nums.size()) { // 如果路径长度等于数组长度,说明已经找到一组解
res.push_back(path); // 将路径加入结果集
return;
}
for (int i = 0; i < nums.size(); i++) {
if (!used[i]) { // 如果当前数字没有被使用过
used[i] = true; // 标记为已使用
path.push_back(nums[i]); // 将当前数字加入路径
dfs(nums, path, used, res); // 继续搜索下一个数字
path.pop_back(); // 回溯,将当前数字从路径中删除
used[i] = false; // 标记为未使用
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res; // 存储结果集
vector<int> path; // 存储路径
vector<bool> used(nums.size(), false); // 标记数字是否被使用过
dfs(nums, path, used, res); // 开始搜索
return res;
}
int main() {
vector<int> nums = {1, 2, 3};
vector<vector<int>> res = permute(nums);
for (auto& path : res) {
for (auto& num : path) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
```