查找总和的潜在数字组合(给定要选择的数字) [英] Finding potential combinations of numbers for a sum (given a number set to select from)

问题描述

我一直在寻找一段时间，以寻求某种解决方案来解决当前正在阻碍我要完成的任务的问题. 我遇到了一些其他编程语言的解决方案，尽管我曾尝试这样做，但这些解决方案我还是听不懂.我还看到了很多围绕此问题的术语，例如排列，重构，子集总和，1美元硬币等.

I've been searching for a while to try and arrive at some sort of solution for a problem that is currently roadblocking a task I'm trying to complete. I've come across a few solutions in other programming languages that I really can't understand despite my attempts at doing so. I've also seen a lot of terminology surrounding this problem such as permutations, refactoring, subset sums, coins in a dollar, etc.

如果我使用错误的方法，请随时告诉我.

If I'm going about this the wrong way, please do feel free to let me know.

简而言之，这就是问题所在:

给出一组数字(数组)， 例如:2, 3, 7, 14， 我怎么能找到这些数字的哪些组合加起来(或等于)一个特定的总和，例如:14.

Given a set (array) of numbers, ex: 2, 3, 7, 14, how could I find what combinations of those numbers add up to (or equal) a specific sum, ex: 14.

上述示例编号的一些可能组合的示例:

An example of some of the potential combinations for the above example numbers:

3 + 3 + 3 + 3 + 2
7 + 3 + 2 + 2
7 + 7
14

由于我要解决的问题是在 PHP 中，因此，我很乐意以该语言提供解决方案.如果不是这样，即使有人可以更好地解释我要解决的问题是什么，以及这样做的潜在方法，我也将不胜感激.

Since the problem I'm trying to solve is in PHP, I'd love if there were a solution that could be offered in that language. If not, even if someone could better explain what the problem is that I'm trying to solve, and potential methods of doing so, I'd be greatly appreciative.

或者再说一次，如果我可能会以错误的方式进行操作，那么我会全神贯注的.

Or again if I might be going about this the wrong way, I'm all ears.

推荐答案

基于amit的反馈和示例以及一些其他示例，到目前为止，这是我设法解决的问题. 到目前为止，它似乎仍然有效-但我不确定100％.

Here's what I have managed to come up with thus far, based on amit's feedback and example, and some other examples. So far it appears to be working - but I'm not 100% certain.

$totals = array();
$x=0;

function getAllCombinations($ind, $denom, $n, $vals=array()){
    global $totals, $x;
    if ($n == 0){
        foreach ($vals as $key => $qty){
            for(; $qty>0; $qty--){
                $totals[$x][] = $denom[$key];
             }
        }
        $x++;
        return;
    }
    if ($ind == count($denom)) return;
    $currdenom = $denom[$ind];
    for ($i=0;$i<=($n/$currdenom);$i++){
        $vals[$ind] = $i;
        getAllCombinations($ind+1,$denom,$n-($i*$currdenom),$vals);
    }
}

$array = array(3, 5, 7, 14);
$sum = 30;

getAllCombinations(0, $array, $sum);

var_dump($totals);

这篇关于查找总和的潜在数字组合(给定要选择的数字)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！