PHP版本，灵感来自Keith Beller的c#版本。

bala的PHP版本不适合我，因为我不需要对数字进行分组。我想要一个更简单的实现，只有一个目标值和一个数字池。这个函数也会删除任何重复的条目。

编辑25/10/2021:添加精度参数以支持浮点数(现在需要bcmath扩展)。

/**
 * Calculates a subset sum: finds out which combinations of numbers
 * from the numbers array can be added together to come to the target
 * number.
 *
 * Returns an indexed array with arrays of number combinations.
 *
 * Example:
 *
 * <pre>
 * $matches = subset_sum(array(5,10,7,3,20), 25);
 * </pre>
 *
 * Returns:
 *
 * <pre>
 * Array
 * (
 *   [0] => Array
 *   (
 *       [0] => 3
 *       [1] => 5
 *       [2] => 7
 *       [3] => 10
 *   )
 *   [1] => Array
 *   (
 *       [0] => 5
 *       [1] => 20
 *   )
 * )
 * </pre>
 *
 * @param number[] $numbers
 * @param number $target
 * @param array $part
 * @param int $precision
 * @return array[number[]]
 */
function subset_sum($numbers, $target, $precision=0, $part=null)
{
    // we assume that an empty $part variable means this
    // is the top level call.
    $toplevel = false;
    if($part === null) {
        $toplevel = true;
        $part = array();
    }

    $s = 0;
    foreach($part as $x)
    {
        $s = $s + $x;
    }

    // we have found a match!
    if(bccomp((string) $s, (string) $target, $precision) === 0)
    {
        sort($part); // ensure the numbers are always sorted
        return array(implode('|', $part));
    }

    // gone too far, break off
    if($s >= $target)
    {
        return null;
    }

    $matches = array();
    $totalNumbers = count($numbers);

    for($i=0; $i < $totalNumbers; $i++)
    {
        $remaining = array();
        $n = $numbers[$i];

        for($j = $i+1; $j < $totalNumbers; $j++)
        {
            $remaining[] = $numbers[$j];
        }

        $part_rec = $part;
        $part_rec[] = $n;

        $result = subset_sum($remaining, $target, $precision, $part_rec);
        if($result)
        {
            $matches = array_merge($matches, $result);
        }
    }

    if(!$toplevel)
    {
        return $matches;
    }

    // this is the top level function call: we have to
    // prepare the final result value by stripping any
    // duplicate results.
    $matches = array_unique($matches);
    $result = array();
    foreach($matches as $entry)
    {
        $result[] = explode('|', $entry);
    }

    return $result;
}

例子:

$result = subset_sum(array(5, 10, 7, 3, 20), 25);

这将返回一个包含两个数字组合数组的索引数组:

3, 5, 7, 10
5, 20

浮点数示例:

// Specify the precision in the third argument
$result = subset_sum(array(0.40, 0.03, 0.05), 0.45, 2);

这将返回一个匹配项:

0.40, 0.05

在Haskell:

filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]

J:

(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...

正如您可能注意到的，两者都采用相同的方法，并将问题分为两部分:生成幂集的每个成员，并检查每个成员与目标的和。

还有其他的解决方案，但这是最直接的。

在这两种方法中，你是否需要帮助，或者找到另一种方法?

这类似于硬币更换问题

public class CoinCount 
{   
public static void main(String[] args)
{
    int[] coins={1,4,6,2,3,5};
    int count=0;

    for (int i=0;i<coins.length;i++)
    {
        count=count+Count(9,coins,i,0);
    }
    System.out.println(count);
}

public static int Count(int Sum,int[] coins,int index,int curSum)
{
    int count=0;

    if (index>=coins.length)
        return 0;

    int sumNow=curSum+coins[index];
    if (sumNow>Sum)
        return 0;
    if (sumNow==Sum)
        return 1;

    for (int i= index+1;i<coins.length;i++)
        count+=Count(Sum,coins,i,sumNow);

    return count;       
}
}

我在做类似的scala作业。我想在这里发布我的解决方案:

 def countChange(money: Int, coins: List[Int]): Int = {
      def getCount(money: Int, remainingCoins: List[Int]): Int = {
        if(money == 0 ) 1
        else if(money < 0 || remainingCoins.isEmpty) 0
        else
          getCount(money, remainingCoins.tail) +
            getCount(money - remainingCoins.head, remainingCoins)
      }
      if(money == 0 || coins.isEmpty) 0
      else getCount(money, coins)
    }

function solve(n){
    let DP = [];

     DP[0] = DP[1] = DP[2] = 1;
     DP[3] = 2;

    for (let i = 4; i <= n; i++) {
      DP[i] = DP[i-1] + DP[i-3] + DP[i-4];
    }
    return DP[n]
}

console.log(solve(5))

这是JS的一个动态解决方案，告诉任何人有多少种方法可以得到一定的总和。如果考虑到时间和空间的复杂性，这可能是正确的解决方案。

Excel VBA版本如下。我需要在VBA中实现这一点(不是我的偏好，不要评判我!)，并使用本页上的答案作为方法。我上传以防其他人也需要VBA版本。

Option Explicit

Public Sub SumTarget()
    Dim numbers(0 To 6)  As Long
    Dim target As Long

    target = 15
    numbers(0) = 3: numbers(1) = 9: numbers(2) = 8: numbers(3) = 4: numbers(4) = 5
    numbers(5) = 7: numbers(6) = 10

    Call SumUpTarget(numbers, target)
End Sub

Public Sub SumUpTarget(numbers() As Long, target As Long)
    Dim part() As Long
    Call SumUpRecursive(numbers, target, part)
End Sub

Private Sub SumUpRecursive(numbers() As Long, target As Long, part() As Long)

    Dim s As Long, i As Long, j As Long, num As Long
    Dim remaining() As Long, partRec() As Long
    s = SumArray(part)

    If s = target Then Debug.Print "SUM ( " & ArrayToString(part) & " ) = " & target
    If s >= target Then Exit Sub

    If (Not Not numbers) <> 0 Then
        For i = 0 To UBound(numbers)
            Erase remaining()
            num = numbers(i)
            For j = i + 1 To UBound(numbers)
                AddToArray remaining, numbers(j)
            Next j
            Erase partRec()
            CopyArray partRec, part
            AddToArray partRec, num
            SumUpRecursive remaining, target, partRec
        Next i
    End If

End Sub

Private Function ArrayToString(x() As Long) As String
    Dim n As Long, result As String
    result = "{" & x(n)
    For n = LBound(x) + 1 To UBound(x)
        result = result & "," & x(n)
    Next n
    result = result & "}"
    ArrayToString = result
End Function

Private Function SumArray(x() As Long) As Long
    Dim n As Long
    SumArray = 0
    If (Not Not x) <> 0 Then
        For n = LBound(x) To UBound(x)
            SumArray = SumArray + x(n)
        Next n
    End If
End Function

Private Sub AddToArray(arr() As Long, x As Long)
    If (Not Not arr) <> 0 Then
        ReDim Preserve arr(0 To UBound(arr) + 1)
    Else
        ReDim Preserve arr(0 To 0)
    End If
    arr(UBound(arr)) = x
End Sub

Private Sub CopyArray(destination() As Long, source() As Long)
    Dim n As Long
    If (Not Not source) <> 0 Then
        For n = 0 To UBound(source)
                AddToArray destination, source(n)
        Next n
    End If
End Sub

输出(写入立即窗口)应该是:

SUM ( {3,8,4} ) = 15
SUM ( {3,5,7} ) = 15
SUM ( {8,7} ) = 15
SUM ( {5,10} ) = 15