你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?

一个简单的例子:

要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345


当前回答

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

其他回答

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

另一个python解决方案是使用itertools.combination模块,如下所示:

#!/usr/local/bin/python

from itertools import combinations

def find_sum_in_list(numbers, target):
    results = []
    for x in range(len(numbers)):
        results.extend(
            [   
                combo for combo in combinations(numbers ,x)  
                    if sum(combo) == target
            ]   
        )   

    print results

if __name__ == "__main__":
    find_sum_in_list([3,9,8,4,5,7,10], 15)

输出:[(8,7),(5,10),(3,8,4),(3,5,7)]

在Haskell:

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

J:

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

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

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

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

下面是一个更好的版本,具有更好的输出格式和c++ 11特性:

void subset_sum_rec(std::vector<int> & nums, const int & target, std::vector<int> & partialNums) 
{
    int currentSum = std::accumulate(partialNums.begin(), partialNums.end(), 0);
    if (currentSum > target)
        return;
    if (currentSum == target) 
    {
        std::cout << "sum([";
        for (auto it = partialNums.begin(); it != std::prev(partialNums.end()); ++it)
            cout << *it << ",";
        cout << *std::prev(partialNums.end());
        std::cout << "])=" << target << std::endl;
    }
    for (auto it = nums.begin(); it != nums.end(); ++it) 
    {
        std::vector<int> remaining;
        for (auto it2 = std::next(it); it2 != nums.end(); ++it2)
            remaining.push_back(*it2);

        std::vector<int> partial = partialNums;
        partial.push_back(*it);
        subset_sum_rec(remaining, target, partial);
    }
}

这个问题的一个迭代c++堆栈解决方案。与其他迭代解决方案不同的是,它不会对中间序列进行不必要的复制。

#include <vector>
#include <iostream>

// Given a positive integer, return all possible combinations of
// positive integers that sum up to it.

std::vector<std::vector<int>> print_all_sum(int target){
    std::vector<std::vector<int>> output;
    std::vector<int> stack;

    int curr_min = 1;
    int sum = 0;
    while (curr_min < target) {
        sum += curr_min;
        if (sum >= target) {
            if (sum == target) {
                output.push_back(stack); // make a copy
                output.back().push_back(curr_min);
            }
            sum -= curr_min + stack.back();
            curr_min = stack.back() + 1;
            stack.pop_back();
        } else {
            stack.push_back(curr_min);
        }
    }

    return output;
}

int main()
{
    auto vvi = print_all_sum(6);

    for (auto const& v: vvi) {
        for(auto const& i: v) {
        std::cout << i;
        }
        std::cout << "\n";
    }

    return 0;
}

输出print_all_sum (6):

111111
11112
1113
1122
114
123
15
222
24
33