PHP 實現數組全組合算法 (生成所有子集)

問題描述

給定數組 [1,2,3,4,5]，生成所有可能的子集組合（冪集），共 2^n 種。

遞歸實現

<?php
$arr = [1,2,3,4,5];
$result = [];

function combine($prefix, $index, $arr, &$result) {
    if ($index === count($arr)) {
        $result[] = $prefix;
        return;
    }
    // 不包含當前元素
    combine($prefix, $index + 1, $arr, $result);
    // 包含當前元素
    combine(array_merge($prefix, [$arr[$index]]), $index + 1, $arr, $result);
}

combine([], 0, $arr, $result);

echo '<pre>';
print_r($result);
echo '</pre>';

迭代實現 (位運算，更高效)

<?php
$arr = [1,2,3,4,5];
$n = count($arr);
$total = 1 << $n; // 2^n
$result = [];

for ($mask = 0; $mask < $total; $mask++) {
    $subset = [];
    for ($i = 0; $i < $n; $i++) {
        if ($mask & (1 << $i)) {
            $subset[] = $arr[$i];
        }
    }
    $result[] = $subset;
}

print_r($result);

應用場景

• 權限角色組合生成。
• 商品屬性 SKU 組合 (顏色×尺寸×套餐)。
• 測試用例全排列覆蓋。
• 背包問題、子集和問題暴力求解 (小規模)。

性能提示

n > 20 時 2^n 爆炸，需改用啟發式/動態規劃/貪心算法，或僅生成滿足條件的組合 (剪枝)。