Please ask me an algorithm problem. Thank you.
there is a set of numbers, for example, 3,
requires that the sum equal to 3 is selected from this group of numbers (3 added numbers). For example, the three added numbers cannot be the same (for example, 1: 1, 1: 1), and there is no order requirement for this group of numbers.
there is a set of numbers [0pm, 2je, 4je, 5pje, 6pje, 7pje, 8pje, 9]. For example, 3, < 3 > requires that the combination equal to 3 (3 added numbers). The
function is roughly like this: fun (array, sum, 3), and you get the number of combinations.
parameter 3 is the number of added numbers, which is specified here as 3, such as 0, 0, 3, which is 3 numbers
.
Recursively find a collection of elements that conform to the rules:
part of the logic is based on the assumption that all elements in the collection are positive
<?php
/**
* @title
* @author start2004
* @since 2018/5/10
*/
/**
* [0,1,2,3,4,5,6,7,8,9],3
* 330+0+3=30+1+231+1+1
* fun(,,3) ,.
* 330+0+33
* https://segmentfault.com/q/1010000014767442?utm_source=tag-newest
*/
ini_set('memory_limit', '8M');
$arr = [0,1,2,3,4,5,6,7,8,9];
$sum = 2;
$num = 3;
$resultArray = calc($arr, $sum, $num);
//var_dump($resultArray);
/**
* @title
* @param array $arr
* @param int $sum
* @param int $num
* @return array
*/
function calc($arr = [], $sum = 0, $num = 0){
$resultArray = main($arr, $sum, $num);
$listArray = [];
if($resultArray){
foreach ($resultArray as $rArray){
/**
* num>1
*
* 1
*/
if ($num=1 OR (array_unique($rArray)) > 1){
/**
*
*/
sort($rArray);
if (in_array($rArray, $listArray) === false){
$listArray[] = $rArray;
echo implode(" + ", $rArray), " = {$sum}", PHP_EOL;
}
}
}
}
/**
*
*/
if (empty($listArray)){
echo "sum = {$sum}, num = {$num}, no result.", PHP_EOL;
}
return $listArray;
}
/**
* @title
* @param array $arr
* @param int $sum
* @param int $num
* @param array $feed
* @return array|bool
*/
function main($arr = [], $sum = 0, $num = 0, $feed = []){
if($num < 1){
return false;
} elseif($num == 1){
/**
* num=1leftSumarr
*/
if(in_array($sum, $arr) !== false){
$feed[] = $sum;
echoLine($sum, $sum, 0, $feed);
return [$feed];
} else {
return false;
}
} else {
$listArray = [];
foreach ($arr as $val){
/**
* sum
*/
if($val <= $sum){
$leftSum = $sum-$val;
$leftNum = $num-1;
$leftFeed = array_merge($feed, [$val]);
echoLine($val, $leftSum, $leftNum, $leftFeed);
$resultArray = main($arr, $leftSum, $leftNum, $leftFeed);
if($resultArray){
foreach ($resultArray as $rArray){
$listArray[] = $rArray;
}
}
}
}
return $listArray;
}
}
/**
* @title
* @param $key
* @param $sum
* @param $num
* @param $feed
*/
function echoLine($key, $sum, $num, $feed){
return ;
$prefix = str_repeat(" ", count($feed)-1);
echo $prefix;
echo "key={$key}";
if($num>0){
echo ", sum={$sum}, num={$num}";
}
echo PHP_EOL;
}
/**
key=0, sum=2, num=2
key=0, sum=2, num=1
key=2
key=1, sum=1, num=1
key=1
key=2, sum=0, num=1
key=0
key=1, sum=1, num=2
key=0, sum=1, num=1
key=1
key=1, sum=0, num=1
key=0
key=2, sum=0, num=2
key=0, sum=0, num=1
key=0
*/
