C++ 穷举算法详解：原理、实现与应用
穷举算法（Brute Force Algorithm）是一种通过遍历所有可能解来求解问题的基本方法，广泛应用于组合优化、搜索问题等领域。在 C++ 中，由于语言的高效性和灵活性，穷举算法成为解决小型或原型问题的有力工具。
一、引言
穷举算法的核心思想是系统地遍历所有可能的候选解，直到找到满足条件的解或穷尽整个解空间。例如，在密码破解中尝试所有字符组合；或在游戏 AI 中枚举所有可能的走法。在 C++ 中，这种算法的重要性体现在其简单性和可靠性上，尤其适用于组合优化问题（如旅行商问题简化版）或搜索任务（如路径查找）。
本文旨在详细讲解 C++ 实现穷举算法的关键技巧，包括递归和迭代方法，分析算法的适用场景和局限性，并提供优化策略。
二、穷举算法的基本原理
穷举算法基于两个核心步骤：问题建模和遍历策略。首先，将问题转化为一个有限的候选解空间。例如，在全排列问题中，解空间是所有可能的排列集合；在子集生成中，解空间是数组的所有子集。其次，通过系统遍历（如递归或迭代）生成并测试每个候选解，直到找到最优解或穷尽空间。
数学基础是理解穷举算法的关键。时间复杂度通常较高，取决于问题规模：
- 对于 $n$ 个元素的排列问题，时间复杂度为 $O(n!)$，因为解空间大小为 $n!$。
- 对于子集生成问题，时间复杂度为 $O(2^n)$，解空间大小为 $2^n$。
- 空间复杂度一般为 $O(n)$，取决于存储中间状态的需求，如使用递归栈或容器存储解。
常见问题类型包括：组合问题（如生成数组的所有子集）、排列问题（如生成数组的所有全排列）、搜索问题（如在迷宫中查找所有路径）。
三、C++ 实现穷举算法
在 C++ 中，穷举算法可通过递归或迭代实现。递归方法利用函数调用栈生成解空间，适合树状结构问题；迭代方法使用循环结构，更适合线性遍历。关键 C++ 特性包括 STL 容器（如 std::vector）、控制结构（for/while 循环）及内存管理。
1. 全排列问题
问题描述：生成数组的所有排列。递归框架通过交换元素和回溯实现。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void permute(vector<int>& nums, int start) {
if (start == nums.size()) {
// 输出当前排列
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return;
}
for ( i = start; i < nums.(); i++) {
(nums[start], nums[i]);
(nums, start + );
(nums[start], nums[i]);
}
}
{
vector<> nums = {, , };
(nums, );
;
}
