PHP实现1到9数字相加等于20的组合算法

问题目标与思路

在程序设计或数学逻辑验证中，常遇到需要从一组整数中提取特定子集的需求。本题要求从数组 [1, 2, 3, 4, 5, 6, 7, 8, 9] 中选取若干个不重复的数字，使得它们的加和严格等于 20。解决方案的核心在于生成所有可能的非重复数字组合，并过滤出满足条件的集合。

核心算法实现

以下PHP代码定义了一个名为 huoqu_zhuhe 的函数，用于获取指定和的组合数。其执行流程分为生成候选集和去重两个主要阶段。

第1步：初始化与参数校验

• 目的：确保输入数据合法，防止运行时错误。
• 动作：检查 $jiashu（加数数组）是否为空或非数组类型；同时验证数组内所有元素是否均为数值型。
• 关键参数：
  • $eq：目标和值（例如 20）。
  • $jiashu：可用数字源数组。
  • $isone：布尔标志，若为 1 表示组合内的数字不可重复使用，0 则允许重复（默认为 1）。

第2步：生成潜在组合字符串

• 入口：以初始数组 $lian 作为起点。
• 操作：采用类似广度优先搜索（BFS）的策略迭代生成组合。
  1. 遍历当前层级的每个组合字符串 $lianstr，将其拆分为数字数组并计算当前总和 $nowhe。
  2. 逐一尝试加入下一个可用数字 $jiashu[$j]。
  3. 若启用不重复模式（$isone==1）且该数字已在当前组合中，则跳过。
  4. 若新总和超过目标值 $eq，中断内层循环（剪枝优化）。
  5. 若新总和等于 $eq，将完整字符串加入结果集 $savearr。
  6. 否则，将新组合字符串加入下一轮迭代队列 $newarr。
• 完成状态：$savearr 中存储了所有按顺序拼接的数字组合字符串（如 "3+8+9"），但可能包含不同顺序导致的重复项（如 "3+8+9" 与 "9+8+3"）。

第3步：去除重复组合

• 目的：消除因添加顺序不同而产生的冗余结果。
• 操作：
  1. 初始化标记数组 $isguolu，默认所有项均保留（值为 0）。
  2. 双重循环比较 $savearr 中的每一对组合。
  3. 若长度不一致，直接跳过。
  4. 将组合拆分为数字数组后，尝试判断两个数组是否包含相同的元素集合（即是否为相同的多重集）。
  5. 若确认两个组合实质相同，则将第二个组合的标记设为 1（舍弃）。
• 完成状态：$isguolu 中标记为 0 的即为唯一的组合。

第4步：输出最终结果

• 操作：遍历 $savearr，仅将 $isguolu[$i]==0 的元素加入 $newarr 并返回。

<?php
function huoqu_zhuhe($eq,$jiashu,$isone=1)
{
    if(empty($jiashu)||!is_array($jiashu)){
        echo 'error:加数必须数组';
        return false;
    }
    $feishu=0;
    for($i=0;$i<count($jiashu);$i++){
        if(!is_numeric($jiashu[$i])){$feishu=1;break;}
    }
    if($feishu==1){
        echo 'error；数组中必须是合法的数字';
        return false;
    }
    $lian=$jiashu;
    $savearr=array();
    while(!empty($lian)){
        $newarr=array();
        $k=0;
        for($i=0;$i<count($lian);$i++){
            $lianstr=$lian[$i];
            $arr=explode('+',$lianstr);
            $nowhe=array_sum($arr);
            for($j=0;$j<count($jiashu);$j++){
                $savestr=$lianstr.'+'.$jiashu[$j];
                if($isone==1&&in_array($jiashu[$j],$arr))continue;
                if(($nowhe+$jiashu[$j])>$eq)break;
                else if(($nowhe+$jiashu[$j])==$eq){
                    $savearr[]=$savestr;
                }
                else{$newarr[$k]=$savestr;$k++;}
            }
        }
        $lian=$newarr;
    }
    // 去重逻辑
    $isguolu=array();
    for($i=0;$i<count($savearr);$i++){
        $isguolu[]=0;
    }
    for($i=0;$i<count($savearr);$i++){
        $arr1=explode('+',$savearr[$i]);
        $len1=count($arr1);
        for($j=$i+1;$j<count($savearr);$j++){
            $arr2=explode('+',$savearr[$j]);
            $len2=count($arr2);
            if($len1!=$len2)continue;
            if($isguolu[$j]==1)continue;
            $jishu=0;
            for($i1=0;$i1<count($arr1);$i1++){
                $a=$arr1[$i1];
                $isyou=0;
                for($i2=$i1;$i2<count($arr2);$i2++){
                    if($a==$arr2[$i2]){
                        $jishu++;
                        $isyou=1;
                        $t=$arr2[$i1];
                        $arr2[$i1]=$arr2[$i2];
                        $arr2[$i2]=$t;
                        break;
                    }
                }
                if($isyou==0)break;
            }
            if($jishu==$len1)$isguolu[$j]=1;
        }
    }
    // 提取最终结果
    $newarr=array();
    for($i=0;$i<count($savearr);$i++){
        if($isguolu[$i]==0)$newarr[]=$savearr[$i];
    }
    return $newarr;
}

// 测试用例
$jiashu=array(1,2,3,4,5,6,7,8,9);
$eq=20;
if($jieguo=huoqu_zhuhe($eq,$jiashu,1)){
    print_r($jieguo);
}
?>

运行结果分析

执行上述代码后，系统将输出一个包含22个元素的数组，列出了所有不重复的有效组合。这些组合涵盖了从3个数字到5个数字的不同情况。具体结果如下：

Array
(
  [0] => 3+8+9
  [1] => 4+7+9
  [2] => 5+6+9
  [3] => 5+7+8
  [4] => 1+2+8+9
  [5] => 1+3+7+9
  [6] => 1+4+6+9
  [7] => 1+4+7+8
  [8] => 1+5+6+8
  [9] => 2+3+6+9
  [10] => 2+3+7+8
  [11] => 2+4+5+9
  [12] => 2+4+6+8
  [13] => 2+5+6+7
  [14] => 3+4+5+8
  [15] => 3+4+6+7
  [16] => 1+2+3+5+9
  [17] => 1+2+3+6+8
  [18] => 1+2+4+5+8
  [19] => 1+2+4+6+7
  [20] => 1+3+4+5+7
  [21] => 2+3+4+5+6
)

以上详细介绍了使用PHP通过排列组合实现1到9数字相加都等于20的方法，更多关于PHP算法优化的资料请关注本站其它相关文章！