简单的排列组合问题——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

一、全排列：n 个元素的所有排列

问题描述：

• 求 [1,2,3] 的所有全排列（如 {1,2,3}、{1,3,2}、{......}，考虑顺序，元素不重复使用）。

算法解析：

1. 确定解空间：n 个元素的所有顺序组合；
2. 确定枚举顺序：三重循环（对应 3 个元素），逐一枚举每个位置的元素，确保元素不重复；
3. 预处理候选解：无
4. 验证有效解：三个位置的元素互不相同；

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3};
    cout << "[" << 1 << "," << 2 << "," << 3 << "]的所有全排列：" << endl;

    // 三重循环枚举所有排列，确保元素不重复
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j == i) continue; // 避免重复选取同一个元素
            for (int k = 0; k < n; ++k) {
                if (k == i || k == j) continue; // 避免重复选取同一个元素
                cout << "{" << nums[i] << ", " << nums[j] << ", " << nums[k] << "}" << endl;
            }
        }
    }
    return 0;
}
        

输出结果

[1,2,3]的所有全排列：
{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}
            

二、部分排列：从 n 个元素中选取 k 个的排列

问题描述：

• 从 [1,2,3,4] 中选取 2 个元素的所有排列（如 {1,2}、{2,1}、{......}，考虑顺序，元素不重复使用）。

算法解析：

1. 确定解空间：n 个元素中选取 k 个的所有顺序组合；
2. 确定枚举顺序：双重循环，外层枚举第一个元素，内层枚举第二个元素（索引与外层不同）；
3. 预处理候选解：无
4. 验证有效解：两个元素的索引不同（确保不重复选取）；

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4};
    int k = 2; // 选取2个元素
    cout << "从[" << 1 << "," << 2 << "," << 3 << "," << 4 << "]中选取" << k << "个的所有排列：" << endl;

    // 枚举所有部分排列（i ≠ j 确保不重复且考虑顺序）
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) continue; // 避免重复选取同一个元素
            cout << "{" << nums[i] << ", " << nums[j] << "}" << endl;
        }
    }
    return 0;
}
        

输出结果

从[1,2,3,4]中选取2个的所有排列：
{1, 2}
{1, 3}
{1, 4}
{2, 1}
{2, 3}
{2, 4}
...（后续省略）
            

三、无重复组合：从 n 个数中选取 k 个的所有组合

问题描述：

• 从 [1,2,3,4] 中选取 2 个数字的所有组合（如 {1,2}、{1,3}，不考虑顺序，不重复选取），属于典型的无重复组合问题。

算法解析：

1. 确定解空间：数组中所有满足 i < j（避免重复组合）的元素对；
2. 确定枚举顺序：双重循环，外层枚举第一个元素，内层枚举第二个元素（索引大于外层）；
3. 预处理候选解：无
4. 验证有效解：仅保留索引递增的组合（确保无重复、无顺序差异）；

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4};
    int k = 2; // 选取2个元素
    cout << "从[" << 1 << "," << 2 << "," << 3 << "," << 4 << "]中选取" << k << "个的所有组合：" << endl;

    // 枚举所有无重复组合（i < j 避免重复）
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            cout << "{" << nums[i] << ", " << nums[j] << "}" << endl;
        }
    }
    return 0;
}  
        

输出结果

从[1,2,3,4]中选取2个的所有组合：
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}
    

四、可重复组合：从 n 个数中选取 k 个的可重复组合

问题描述：

• 从 [1,2,3] 中选取 2 个数字的可重复组合（如 {1,1}、{1,2}，不考虑顺序，允许重复选取），常见于 “物品可重复选取” 的场景。

算法解析：

1. 确定解空间：数组中所有满足 i ≤ j（允许重复、避免顺序差异）的元素对；
2. 确定枚举顺序：双重循环，外层枚举第一个元素，内层枚举第二个元素（索引大于等于外层）；
3. 预处理候选解：无
4. 验证有效解：保留索引非递减的组合（确保可重复、无顺序差异）；

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3};
    int k = 2; // 选取2个元素
    cout << "从[" << 1 << "," << 2 << "," << 3 << "]中选取" << k << "个的可重复组合：" << endl;

    // 枚举所有可重复组合（i ≤ j 允许重复且避免顺序差异）
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            cout << "{" << nums[i] << ", " << nums[j] << "}" << endl;
        }
    }
    return 0;
} 
        

输出结果

从[1,2,3]中选取2个的可重复组合：
{1, 1}
{1, 2}
{1, 3}
{2, 2}
{2, 3}
{3, 3}
            

五、 字符组合：生成指定长度的字符组合（可重复）

问题描述：

• 从字符集 {'a','b','c'} 中生成长度为 2 的所有可重复字符组合（如 "aa"、"ab"），常见于简单密码枚举、字符拼接场景。

算法解析：

1. 确定解空间：字符集的所有长度为 k 的拼接组合；
2. 确定枚举顺序：双重循环，分别枚举第 1 位和第 2 位字符；
3. 预处理候选解：无
4. 验证有效解：无额外条件（允许重复字符）；

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    vector<char> chars = {'a', 'b', 'c'};
    int len = 2; // 组合长度
    cout << "从{'a','b','c'}中生成长度为" << len << "的可重复字符组合：" << endl;

    // 枚举所有字符组合
    int n = chars.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            string combo;
            combo += chars[i];
            combo += chars[j];
            cout << "\"" << combo << "\"" << endl;
        }
    }
    return 0;
}
        

输出结果

从{'a','b','c'}中生成长度为2的可重复字符组合：
"aa"
"ab"
"ac"
"ba"
"bb"
"bc"
"ca"
"cb"
"cc"
            

六、 组合求和：查找和为指定值的 k 元素组合（无重复）

问题描述：

• 从 [1,2,3,4,5] 中选取 2 个元素，查找所有和为 6 的组合（如 {1,5}、{2,4}），属于 “带条件的组合问题”。

算法解析：

1. 确定解空间：所有 k 元素无重复组合（i < j）；
2. 确定枚举顺序：双重循环枚举 i < j 的元素对；
3. 预处理候选解：无
4. 验证有效解：元素和等于目标值；

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    int k = 2; // 选取2个元素
    int targetSum = 6; // 目标和
    cout << "从[" << 1 << "," << 2 << "," << 3 << "," << 4 << "," << 5 << "]中选取" << k << "个和为" << targetSum << "的组合：" << endl;

    // 枚举无重复组合，筛选和为目标值的结果
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (nums[i] + nums[j] == targetSum) {
                cout << "{" << nums[i] << ", " << nums[j] << "}" << endl;
            }
        }
    }
    return 0;
}
        

输出结果

从[1,2,3,4,5]中选取2个和为6的组合：
{1, 5}
{2, 4}
            

七、总结

枚举算法解决简单组合 / 排列问题的共性特点：

1. 数据规模小（元素个数通常≤5，组合 / 排列长度≤3），枚举效率可接受；
2. 实现简单：通过多层循环直接遍历所有候选，无需递归或高级算法；
3. 边界清晰：通过索引判断（i < j / i ≤ j / i ≠ j）区分 “无重复 / 可重复 / 考虑顺序”；
4. 灵活扩展：可通过增加筛选条件（如和为指定值）适配带约束的组合 / 排列场景。

上述实例覆盖了数值、字符、带条件等常见场景，适合入门者理解组合 / 排列的本质及枚举算法的应用。