PHP实现带分组限制的字符串所有可能组合生成算法求助

安全阿岳

2026-5-29

解决带分组限制的字母组合划分问题

我来帮你实现这个符合要求的PHP算法！先明确下核心需求：我们需要把输入的字母数组划分成若干子分组，每个子分组必须在允许的分组列表里（单个字母默认合法），同时所有子分组的字母合并后和原数组完全一致，没有重复或遗漏。

思路分析

这本质是带约束的集合划分问题，用回溯（递归）的方式来生成所有可能的合法组合最直观：

先预处理允许的分组，把单个字母也加入允许集合（因为示例里单个字母是合法的），方便快速校验。
递归过程中，每次从剩余字母里取第一个元素，只考虑包含这个元素的合法分组（避免生成重复或乱序的组合）。
对每个合法分组，从剩余字母中移除该分组的所有字母，继续递归处理剩下的字母，直到剩余字母为空时，把当前组合加入结果集。

PHP代码实现

function generateValidCombinations($letters, $allowedGroups) {
    // 把允许分组转为哈希集合，同时添加单个字母（默认合法）
    $allowedSet = array_flip($allowedGroups);
    foreach ($letters as $letter) {
        $allowedSet[$letter] = true;
    }

    $result = [];

    // 回溯递归函数
    $backtrack = function($remaining, $current) use (&$result, $allowedSet, &$backtrack) {
        // 剩余字母为空，说明找到一个合法组合
        if (empty($remaining)) {
            $result[] = $current;
            return;
        }

        $firstLetter = $remaining[0];
        // 遍历所有包含第一个字母的允许分组
        foreach ($allowedSet as $group => $_) {
            // 分组不包含当前剩余的第一个字母，跳过
            if (strpos($group, $firstLetter) === false) {
                continue;
            }
            // 拆分分组为单个字母
            $groupLetters = str_split($group);
            // 检查分组的所有字母都在剩余字母中
            if (!empty(array_diff($groupLetters, $remaining))) {
                continue;
            }
            // 计算新的剩余字母：移除当前分组的所有字母
            $newRemaining = array_values(array_diff($remaining, $groupLetters));
            // 递归处理新的剩余字母，同时把当前分组加入组合
            $backtrack($newRemaining, array_merge($current, [$group]));
        }
    };

    // 初始调用：剩余字母为原数组，当前组合为空
    $backtrack($letters, []);

    return $result;
}

// 测试示例
$inputLetters = ['A', 'B', 'C'];
$allowedGroups = ['AB', 'BC'];
$validCombinations = generateValidCombinations($inputLetters, $allowedGroups);

// 打印结果
print_r($validCombinations);

代码说明

预处理阶段：用array_flip把允许分组数组转成键为分组的哈希表，O(1)时间就能判断一个分组是否合法；同时把每个单个字母加入允许集合，确保单个字母的组合合法。
回溯逻辑：每次只处理包含剩余字母第一个元素的分组，这样能保证组合的顺序符合原字母的顺序，避免生成重复的组合（比如不会出现['C','AB']这种乱序组合）。
合法性校验：通过array_diff检查分组的所有字母是否都在剩余字母中，确保不会使用超出剩余范围的字母，也不会出现重复字母的组合。

测试结果

运行上面的代码，输出和你给出的示例完全一致：

Array
(
    [0] => Array
        (
            [0] => A
            [1] => B
            [2] => C
        )

    [1] => Array
        (
            [0] => A
            [1] => BC
        )

    [2] => Array
        (
            [0] => AB
            [1] => C
        )
)

如果需要调整组合的输出顺序，可以在最后对$result进行排序，比如按组合的长度排序，或者按分组的字典序排序。

内容的提问来源于stack exchange，提问作者user1744228