你如何从给定的N个数字中测试所有可能的加法组合，使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0，…} 期望结果:12345
当前回答
Java非递归版本，简单地添加元素并在可能的值之间重新分配它们。0被忽略，适用于固定的列表(给定的是您可以使用的)或可重复的数字列表。
import java.util.*;
public class TestCombinations {
public static void main(String[] args) {
ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(0, 1, 2, 2, 5, 10, 20));
LinkedHashSet<Integer> targets = new LinkedHashSet<Integer>() {{
add(4);
add(10);
add(25);
}};
System.out.println("## each element can appear as many times as needed");
for (Integer target: targets) {
Combinations combinations = new Combinations(numbers, target, true);
combinations.calculateCombinations();
for (String solution: combinations.getCombinations()) {
System.out.println(solution);
}
}
System.out.println("## each element can appear only once");
for (Integer target: targets) {
Combinations combinations = new Combinations(numbers, target, false);
combinations.calculateCombinations();
for (String solution: combinations.getCombinations()) {
System.out.println(solution);
}
}
}
public static class Combinations {
private boolean allowRepetitions;
private int[] repetitions;
private ArrayList<Integer> numbers;
private Integer target;
private Integer sum;
private boolean hasNext;
private Set<String> combinations;
/**
* Constructor.
*
* @param numbers Numbers that can be used to calculate the sum.
* @param target Target value for sum.
*/
public Combinations(ArrayList<Integer> numbers, Integer target) {
this(numbers, target, true);
}
/**
* Constructor.
*
* @param numbers Numbers that can be used to calculate the sum.
* @param target Target value for sum.
*/
public Combinations(ArrayList<Integer> numbers, Integer target, boolean allowRepetitions) {
this.allowRepetitions = allowRepetitions;
if (this.allowRepetitions) {
Set<Integer> numbersSet = new HashSet<>(numbers);
this.numbers = new ArrayList<>(numbersSet);
} else {
this.numbers = numbers;
}
this.numbers.removeAll(Arrays.asList(0));
Collections.sort(this.numbers);
this.target = target;
this.repetitions = new int[this.numbers.size()];
this.combinations = new LinkedHashSet<>();
this.sum = 0;
if (this.repetitions.length > 0)
this.hasNext = true;
else
this.hasNext = false;
}
/**
* Calculate and return the sum of the current combination.
*
* @return The sum.
*/
private Integer calculateSum() {
this.sum = 0;
for (int i = 0; i < repetitions.length; ++i) {
this.sum += repetitions[i] * numbers.get(i);
}
return this.sum;
}
/**
* Redistribute picks when only one of each number is allowed in the sum.
*/
private void redistribute() {
for (int i = 1; i < this.repetitions.length; ++i) {
if (this.repetitions[i - 1] > 1) {
this.repetitions[i - 1] = 0;
this.repetitions[i] += 1;
}
}
if (this.repetitions[this.repetitions.length - 1] > 1)
this.repetitions[this.repetitions.length - 1] = 0;
}
/**
* Get the sum of the next combination. When 0 is returned, there's no other combinations to check.
*
* @return The sum.
*/
private Integer next() {
if (this.hasNext && this.repetitions.length > 0) {
this.repetitions[0] += 1;
if (!this.allowRepetitions)
this.redistribute();
this.calculateSum();
for (int i = 0; i < this.repetitions.length && this.sum != 0; ++i) {
if (this.sum > this.target) {
this.repetitions[i] = 0;
if (i + 1 < this.repetitions.length) {
this.repetitions[i + 1] += 1;
if (!this.allowRepetitions)
this.redistribute();
}
this.calculateSum();
}
}
if (this.sum.compareTo(0) == 0)
this.hasNext = false;
}
return this.sum;
}
/**
* Calculate all combinations whose sum equals target.
*/
public void calculateCombinations() {
while (this.hasNext) {
if (this.next().compareTo(target) == 0)
this.combinations.add(this.toString());
}
}
/**
* Return all combinations whose sum equals target.
*
* @return Combinations as a set of strings.
*/
public Set<String> getCombinations() {
return this.combinations;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder("" + sum + ": ");
for (int i = 0; i < repetitions.length; ++i) {
for (int j = 0; j < repetitions[i]; ++j) {
stringBuilder.append(numbers.get(i) + " ");
}
}
return stringBuilder.toString();
}
}
}
样例输入:
numbers: 0, 1, 2, 2, 5, 10, 20
targets: 4, 10, 25
样例输出:
## each element can appear as many times as needed
4: 1 1 1 1
4: 1 1 2
4: 2 2
10: 1 1 1 1 1 1 1 1 1 1
10: 1 1 1 1 1 1 1 1 2
10: 1 1 1 1 1 1 2 2
10: 1 1 1 1 2 2 2
10: 1 1 2 2 2 2
10: 2 2 2 2 2
10: 1 1 1 1 1 5
10: 1 1 1 2 5
10: 1 2 2 5
10: 5 5
10: 10
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
25: 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
25: 1 1 1 2 2 2 2 2 2 2 2 2 2 2
25: 1 2 2 2 2 2 2 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 5
25: 1 1 1 1 1 1 1 1 2 2 2 2 2 2 5
25: 1 1 1 1 1 1 2 2 2 2 2 2 2 5
25: 1 1 1 1 2 2 2 2 2 2 2 2 5
25: 1 1 2 2 2 2 2 2 2 2 2 5
25: 2 2 2 2 2 2 2 2 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 5
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 5 5
25: 1 1 1 1 1 1 1 1 1 2 2 2 5 5
25: 1 1 1 1 1 1 1 2 2 2 2 5 5
25: 1 1 1 1 1 2 2 2 2 2 5 5
25: 1 1 1 2 2 2 2 2 2 5 5
25: 1 2 2 2 2 2 2 2 5 5
25: 1 1 1 1 1 1 1 1 1 1 5 5 5
25: 1 1 1 1 1 1 1 1 2 5 5 5
25: 1 1 1 1 1 1 2 2 5 5 5
25: 1 1 1 1 2 2 2 5 5 5
25: 1 1 2 2 2 2 5 5 5
25: 2 2 2 2 2 5 5 5
25: 1 1 1 1 1 5 5 5 5
25: 1 1 1 2 5 5 5 5
25: 1 2 2 5 5 5 5
25: 5 5 5 5 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 10
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 10
25: 1 1 1 1 1 1 1 1 1 2 2 2 10
25: 1 1 1 1 1 1 1 2 2 2 2 10
25: 1 1 1 1 1 2 2 2 2 2 10
25: 1 1 1 2 2 2 2 2 2 10
25: 1 2 2 2 2 2 2 2 10
25: 1 1 1 1 1 1 1 1 1 1 5 10
25: 1 1 1 1 1 1 1 1 2 5 10
25: 1 1 1 1 1 1 2 2 5 10
25: 1 1 1 1 2 2 2 5 10
25: 1 1 2 2 2 2 5 10
25: 2 2 2 2 2 5 10
25: 1 1 1 1 1 5 5 10
25: 1 1 1 2 5 5 10
25: 1 2 2 5 5 10
25: 5 5 5 10
25: 1 1 1 1 1 10 10
25: 1 1 1 2 10 10
25: 1 2 2 10 10
25: 5 10 10
25: 1 1 1 1 1 20
25: 1 1 1 2 20
25: 1 2 2 20
25: 5 20
## each element can appear only once
4: 2 2
10: 1 2 2 5
10: 10
25: 1 2 2 20
25: 5 20
其他回答
另一个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)]
这个问题的解决方案在互联网上已经出现过无数次了。这个问题叫做硬币兑换问题。你可以在http://rosettacode.org/wiki/Count_the_coins上找到答案，在http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf上找到数学模型(或谷歌硬币变化问题)。
顺便说一下，Tsagadai的Scala解决方案很有趣。本例生成1或0。作为一个副作用，它在控制台上列出了所有可能的解决方案。它显示解决方案，但无法以任何方式使其可用。
为了尽可能有用，代码应该返回一个List[List[Int]]，以允许获得解决方案的数量(列表列表的长度)，“最佳”解决方案(最短的列表)，或所有可能的解决方案。
这里有一个例子。它效率很低，但很容易理解。
object Sum extends App {
def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = {
def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = {
(x._1 + y._1, x._2 ::: y._2)
}
def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = {
if (numbers.isEmpty || total < 0) {
(0, resultAcc)
} else if (total == 0) {
(1, sumAcc :: resultAcc)
} else {
add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers))
}
}
sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2
}
println(sumCombinations(15, List(1, 2, 5, 10)) mkString "\n")
}
运行时，它显示:
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
List(1, 1, 1, 2, 2, 2, 2, 2, 2)
List(1, 2, 2, 2, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5)
List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5)
List(1, 1, 1, 1, 1, 1, 2, 2, 5)
List(1, 1, 1, 1, 2, 2, 2, 5)
List(1, 1, 2, 2, 2, 2, 5)
List(2, 2, 2, 2, 2, 5)
List(1, 1, 1, 1, 1, 5, 5)
List(1, 1, 1, 2, 5, 5)
List(1, 2, 2, 5, 5)
List(5, 5, 5)
List(1, 1, 1, 1, 1, 10)
List(1, 1, 1, 2, 10)
List(1, 2, 2, 10)
List(5, 10)
sumcombination()函数可以单独使用，并且可以进一步分析结果以显示“最佳”解决方案(最短的列表)或解决方案的数量(列表的数量)。
请注意，即使这样，需求也可能无法完全满足。解决方案中每个列表的顺序可能是重要的。在这种情况下，每个列表都必须重复它的元素组合的次数。或者我们只对不同的组合感兴趣。
例如，我们可以考虑List(5,10)应该给出两种组合:List(5,10)和List(10,5)。对于List(5,5,5)，它可以给出三种组合，也可以只给出一种组合，这取决于需求。对于整数，这三种排列是等价的，但如果我们处理的是硬币，就像在“硬币更换问题”中一样，它们就不一样了。
Also not stated in the requirements is the question of whether each number (or coin) may be used only once or many times. We could (and we should!) generalize the problem to a list of lists of occurrences of each number. This translates in real life into "what are the possible ways to make an certain amount of money with a set of coins (and not a set of coin values)". The original problem is just a particular case of this one, where we have as many occurrences of each coin as needed to make the total amount with each single coin value.
我在做类似的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)
}
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
非常有效的算法，使用我几年前用c++写的表格。
如果你设置PRINT 1，它将打印所有的组合(但它不会使用有效的方法)。
它非常高效，在不到10毫秒的时间内计算了超过10^14个组合。
#include <stdio.h>
#include <stdlib.h>
//#include "CTime.h"
#define SUM 300
#define MAXNUMsSIZE 30
#define PRINT 0
long long CountAddToSum(int,int[],int,const int[],int);
void printr(const int[], int);
long long table1[SUM][MAXNUMsSIZE];
int main()
{
int Nums[]={3,4,5,6,7,9,13,11,12,13,22,35,17,14,18,23,33,54};
int sum=SUM;
int size=sizeof(Nums)/sizeof(int);
int i,j,a[]={0};
long long N=0;
//CTime timer1;
for(i=0;i<SUM;++i)
for(j=0;j<MAXNUMsSIZE;++j)
table1[i][j]=-1;
N = CountAddToSum(sum,Nums,size,a,0); //algorithm
//timer1.Get_Passd();
//printf("\nN=%lld time=%.1f ms\n", N,timer1.Get_Passd());
printf("\nN=%lld \n", N);
getchar();
return 1;
}
long long CountAddToSum(int s, int arr[],int arrsize, const int r[],int rsize)
{
static int totalmem=0, maxmem=0;
int i,*rnew;
long long result1=0,result2=0;
if(s<0) return 0;
if (table1[s][arrsize]>0 && PRINT==0) return table1[s][arrsize];
if(s==0)
{
if(PRINT) printr(r, rsize);
return 1;
}
if(arrsize==0) return 0;
//else
rnew=(int*)malloc((rsize+1)*sizeof(int));
for(i=0;i<rsize;++i) rnew[i]=r[i];
rnew[rsize]=arr[arrsize-1];
result1 = CountAddToSum(s,arr,arrsize-1,rnew,rsize);
result2 = CountAddToSum(s-arr[arrsize-1],arr,arrsize,rnew,rsize+1);
table1[s][arrsize]=result1+result2;
free(rnew);
return result1+result2;
}
void printr(const int r[], int rsize)
{
int lastr=r[0],count=0,i;
for(i=0; i<rsize;++i)
{
if(r[i]==lastr)
count++;
else
{
printf(" %d*%d ",count,lastr);
lastr=r[i];
count=1;
}
}
if(r[i-1]==lastr) printf(" %d*%d ",count,lastr);
printf("\n");
}
