PHP 找出 1-9 中和為 20 的所有不重複組合

問題描述

從數字集合 {1,2,3,4,5,6,7,8,9} 中任意選取若干個數（每個數最多用一次），使其和等於 20，求所有可能的組合。

算法思路：排列生成 + 去重

1. 廣度優先構建排列：從空序列開始，每輪在現有序列後追加一個可用數字，若和超過 20 剪枝，等於 20 記錄結果；
2. 去重策略：將每個結果排序後作為鍵存入關聯數組，自動去除順序不同但元素相同的重複組合（如 3+8+9 與 9+3+8）。

完整實現代碼

 $target) continue; // 剪枝
                $newSeq = $seq . '+' . $num;
                if ($newSum === $target) {
                    $results[] = $newSeq;
                } else {
                    $next[] = $newSeq;
                }
            }
        }
        $sequences = $next;
    }

    // 去重：排序後作為 key
    $uniqueResults = [];
    foreach ($results as $r) {
        $arr = explode('+', $r);
        sort($arr, SORT_NUMERIC);
        $key = implode('+', $arr);
        $uniqueResults[$key] = $r; // 保留原始順序的一種
    }

    return array_values($uniqueResults);
}

// 測試
$numbers = range(1, 9);
$target = 20;
$combinations = findCombinations($target, $numbers, true);

echo "目標和：$target\n";
echo "可用數字：" . implode(',', $numbers) . "\n";
echo "共找到 " . count($combinations) . " 種組合：\n";
foreach ($combinations as $i => $c) {
    echo ($i+1) . ". $c\n";
}

運行結果

目標和：20
可用數字：1,2,3,4,5,6,7,8,9
共找到 22 種組合：
1. 3+8+9
2. 4+7+9
3. 5+6+9
4. 5+7+8
5. 1+2+8+9
6. 1+3+7+9
7. 1+4+6+9
8. 1+4+7+8
9. 1+5+6+8
10. 2+3+6+9
11. 2+3+7+8
12. 2+4+5+9
13. 2+4+6+8
14. 2+5+6+7
15. 3+4+5+8
16. 3+4+6+7
17. 1+2+3+5+9
18. 1+2+3+6+8
19. 1+2+4+5+8
20. 1+2+4+6+7
21. 1+3+4+5+7
22. 2+3+4+5+6

複雜度分析與優化

• 時間複雜度：最壞情況接近 O(k * n^k)（k 為組合長度，n=9），實際受目標和剪枝影響較小；
• 空間複雜度：主要佔用中間序列數組與結果集；
• 優化方向：

1. 改用遞歸回溯 + 剪枝，代碼更簡潔，避免中間數組拷貝；
2. 數字集較大時可引入動態規劃或生成函數數學方法；
3. 去重改用位掩碼（9 位整數）作為鍵，效率更高。

遞歸回溯版本（推薦）

function combineRecursive($target, $numbers, $start = 0, $path = [], &$results = []) {
    if ($target === 0) {
        $results[] = implode('+', $path);
        return;
    }
    for ($i = $start; $i < count($numbers); $i++) {
        $num = $numbers[$i];
        if ($num > $target) break; // 數組已排序，後續更大直接跳出
        $path[] = $num;
        combineRecursive($target - $num, $numbers, $i + 1, $path, $results);
        array_pop($path);
    }
}
$results = [];
combineRecursive(20, range(1,9), 0, [], $results);
print_r($results);

此版本天然保證組合內數字遞增、無重複、無順序重複，代碼極其精簡高效。