深度优先搜索求解全排列c++

深度优先搜索（Depth-First Search, DFS）通常用于图或树的遍历，但它并非直接用于求解全排列。然而，DFS 可以被用来生成排列的一种方法，特别是当涉及到排列组合问题时。以下是一个简单的 C++ 实现，使用递归和深度优先搜索来生成一个数组的所有可能排列：

#include <vector>
#include <iostream>

std::vector<int> permute(std::vector<int>& nums) {
    if (nums.empty()) return {};

    std::vector<std::vector<int>> res;
    permuteDFS(nums, 0, res);
    return res;
}

void permuteDFS(std::vector<int>& nums, int start, std::vector<std::vector<int>>& res) {
    if (start == nums.size()) {
        res.push_back(nums);
        return;
    }

    for (int i = start; i < nums.size(); ++i) {
        std::swap(nums[start], nums[i]); // 交换当前元素
        permuteDFS(nums, start + 1, res); // 递归处理剩余元素
        std::swap(nums[start], nums[i]); // 回溯，恢复初始状态
    }
}

int main() {
    std::vector<int> nums = {1, 2, 3};
    std::vector<std::vector<int>> permutations = permute(nums);

    for (const auto& permutation : permutations) {
        for (int num : permutation) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    }

    return 0;
}

在这个代码中，`permute` 函数是主入口，它调用 `permuteDFS` 进行深度优先搜索。`permuteDFS` 通过递归将每个元素与后面的元素交换位置，直到所有元素都出现在第一位，然后回溯到上一层，继续处理下一个未处理的元素。