C++排列组合算法详解（从零开始掌握C++实现排列组合的多种方法）

方法一：使用递归实现全排列

递归是理解排列组合递归算法最直观的方式。我们通过交换元素位置来生成所有可能的排列。

#include <iostream>#include <vector>using namespace std;void permute(vector<int>& nums, int start, vector<vector<int>>& result) {    if (start == nums.size()) {        result.push_back(nums);        return;    }    for (int i = start; i < nums.size(); ++i) {        swap(nums[start], nums[i]);        permute(nums, start + 1, result);        swap(nums[start], nums[i]); // 回溯    }}int main() {    vector<int> nums = {1, 2, 3};    vector<vector<int>> result;    permute(nums, 0, result);    cout << "All permutations:\n";    for (auto& p : result) {        for (int x : p) {            cout << x << " ";        }        cout << "\n";    }    return 0;}

这段代码使用回溯思想，在每一步固定一个位置，然后递归处理剩余部分。注意两次 swap 是为了恢复原状态，这是回溯的关键。

方法二：使用 STL 的 next_permutation

C++ 标准库提供了强大的工具：std::next_permutation，可以轻松生成字典序下一个排列。这是实现C++ STL next_permutation功能的最简洁方式。

#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() {    vector<int> nums = {1, 2, 3};    sort(nums.begin(), nums.end()); // 必须先排序    cout << "All permutations using STL:\n";    do {        for (int x : nums) {            cout << x << " ";        }        cout << "\n";    } while (next_permutation(nums.begin(), nums.end()));    return 0;}

注意：使用 next_permutation 前必须对数组进行排序，否则会漏掉一些排列。

方法三：递归实现组合

组合不需要考虑顺序，我们可以用“选或不选”的思路来递归。

#include <iostream>#include <vector>using namespace std;void combine(vector<int>& nums, int start, int k,              vector<int>& current, vector<vector<int>>& result) {    if (k == 0) {        result.push_back(current);        return;    }    for (int i = start; i <= (int)nums.size() - k; ++i) {        current.push_back(nums[i]);        combine(nums, i + 1, k - 1, current, result);        current.pop_back(); // 回溯    }}int main() {    vector<int> nums = {1, 2, 3, 4};    int k = 2;    vector<vector<int>> result;    vector<int> current;    combine(nums, 0, k, current, result);    cout << "All combinations of " << k << " elements:\n";    for (auto& c : result) {        for (int x : c) {            cout << x << " ";        }        cout << "\n";    }    return 0;}

总结

本文详细介绍了三种实现C++排列组合算法的方法：

• 递归+回溯实现全排列
• 使用 STL 的 next_permutation 函数
• 递归实现组合（不考虑顺序）

无论你是算法初学者还是希望复习基础知识，掌握这些方法都能帮助你高效解决实际问题。建议多动手写代码，加深理解！