给定一组数字：{1，3，2，5，4，9}，找到总和为特定值（例如此示例中的9）的子集数量。
这类似于子集总和问题，但稍有不同的是，我们要找到这样的子集数量，而不是检查集合是否有总和为9的子集。我正在遵循这里子集总和问题的解决方案。但我想知道如何修改它以返回子集的数量。
18个回答
37
def total_subsets_matching_sum(numbers, sum):
array = [1] + [0] * (sum)
for current_number in numbers:
for num in xrange(sum - current_number, -1, -1):
if array[num]:
array[num + current_number] += array[num]
return array[sum]
assert(total_subsets_matching_sum(range(1, 10), 9) == 8)
assert(total_subsets_matching_sum({1, 3, 2, 5, 4, 9}, 9) == 4)
说明
这是一个经典问题之一。这个想法是找到当前数字的可能总和数量。事实证明，将总和归零确实有一种方法。一开始，我们只有一个数字。我们从目标（解决方案中的变量Maximum）开始减去那个数字。如果可以得到该数字的总和（对应于该数字的数组元素不为零），则将其加到当前数字对应的数组元素中。这样编写程序会更容易理解。
for current_number in numbers:
for num in xrange(sum, current_number - 1, -1):
if array[num - current_number]:
array[num] += array[num - current_number]
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
现在，第二个数字是2。我们从9开始减去2，但不是有效的（因为7的数组元素为零，我们跳过它），我们一直这样做直到3。 当它是3时，3-2是1，与1对应的数组元素是1，我们将其添加到3的数组元素中。 当它是2时，2-2变成0，我们将对应于0的值添加到2的数组元素中。 在此迭代之后，数组如下所示
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 2, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 2, 2, 2, 2, 2, 1, 1]
[1, 1, 1, 2, 2, 3, 3, 3, 3, 3]
[1, 1, 1, 2, 2, 3, 4, 4, 4, 5]
[1, 1, 1, 2, 2, 3, 4, 5, 5, 6]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 7]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 8]
在最后一次迭代之后，我们将考虑所有数字，并且获得目标的方法数将是与目标值对应的数组元素。在我们的例子中，最后一次迭代后Array[9]是8。
- thefourtheye
10
2如果列表中包含负数，会怎么样？ - Ayush choubey
1@Suri 我没有使用 OP 的输入。我使用的是从 1 到 9 的数字。
Numbers 变量包含实际使用的输入。 - thefourtheye1谢谢您的纠正。我已经点赞了您的回答。我们有一个问题，我们输入1、3、2、5、4、9，然后将其排序为1、2、3、4、5、9，然后应用我们的算法。我们能否不进行排序？第二个问题是，如果我们有重复的数字，我们该如何处理这个算法？您能提供一下这个算法吗？ - Suri
11问题是：“给定一组数字……” 集合不包含重复的元素。因此，解决方案无需处理重复项。 - Kyle Robson
@user177196 这意味着如果不是零（我相信），但无论如何它都是Python，你可以检查一下。 - user3494047
显示剩余5条评论
19
你可以使用动态规划。算法复杂度为O(Sum * N)，并且使用O(Sum)的内存。
这是我在C#中的实现：
private static int GetmNumberOfSubsets(int[] numbers, int sum)
{
int[] dp = new int[sum + 1];
dp[0] = 1;
int currentSum =0;
for (int i = 0; i < numbers.Length; i++)
{
currentSum += numbers[i];
for (int j = Math.Min(sum, currentSum); j >= numbers[i]; j--)
dp[j] += dp[j - numbers[i]];
}
return dp[sum];
}
注意：由于子集的数量可能达到2^N，它很容易会超出int类型的范围。
该算法仅适用于正数。
- Толя
2
这里可以降低内存需求吗？ - Anirudh
不，这是不可能的。解决方案基于内存使用。 - Толя
12
这里是一个Java解法：
这是一个经典的回溯问题，用于查找整数数组或集合输入的所有可能子集，然后筛选出总和为给定目标值的子集。
import java.util.HashSet;
import java.util.StringTokenizer;
/**
* Created by anirudh on 12/5/15.
*/
public class findSubsetsThatSumToATarget {
/**
* The collection for storing the unique sets that sum to a target.
*/
private static HashSet<String> allSubsets = new HashSet<>();
/**
* The String token
*/
private static final String token = " ";
/**
* The method for finding the subsets that sum to a target.
*
* @param input The input array to be processed for subset with particular sum
* @param target The target sum we are looking for
* @param ramp The Temporary String to be beefed up during recursive iterations(By default value an empty String)
* @param index The index used to traverse the array during recursive calls
*/
public static void findTargetSumSubsets(int[] input, int target, String ramp, int index) {
if(index > (input.length - 1)) {
if(getSum(ramp) == target) {
allSubsets.add(ramp);
}
return;
}
//First recursive call going ahead selecting the int at the currenct index value
findTargetSumSubsets(input, target, ramp + input[index] + token, index + 1);
//Second recursive call going ahead WITHOUT selecting the int at the currenct index value
findTargetSumSubsets(input, target, ramp, index + 1);
}
/**
* A helper Method for calculating the sum from a string of integers
*
* @param intString the string subset
* @return the sum of the string subset
*/
private static int getSum(String intString) {
int sum = 0;
StringTokenizer sTokens = new StringTokenizer(intString, token);
while (sTokens.hasMoreElements()) {
sum += Integer.parseInt((String) sTokens.nextElement());
}
return sum;
}
/**
* Cracking it down here : )
*
* @param args command line arguments.
*/
public static void main(String[] args) {
int [] n = {24, 1, 15, 3, 4, 15, 3};
int counter = 1;
FindSubsetsThatSumToATarget.findTargetSumSubsets(n, 25, "", 0);
for (String str: allSubsets) {
System.out.println(counter + ") " + str);
counter++;
}
}
}
它会给出空格分隔的子集值，其总和为目标值。
在{24, 1, 15, 3, 4, 15, 3}中，将打印出所有总和为25的子集，其中数字之间用逗号分隔：
1) 24, 1
2) 3, 4, 15, 3
3) 15, 3, 4, 3
- Anirudh
3
1这就是我需要的，谢谢Anirudh。 - bebosh
该算法的时间复杂度是2^N吗？ - user1477232
@user1477232 总的来说，这个问题是NP完全问题，但是伪多项式。请查看我在另一个解决方案中对Ignacio Tartavul的问题的评论以获取更多详细信息。 - rocky
7
同样的网站geeksforgeeks还讨论了输出所有子集总和为特定值的解决方案：http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/
在您的情况下，您只需要计算它们而不是输出集合。请务必检查同一页中的优化版本，因为这是一个NP完全问题。
此问题以前也曾在stackoverflow上提出并回答过，但没有提到它是一个子集和问题：Finding all possible combinations of numbers to reach a given sum。
此问题以前也曾在stackoverflow上提出并回答过，但没有提到它是一个子集和问题：Finding all possible combinations of numbers to reach a given sum。
- kaisernahid
7
我用Java解决了这个问题。这个解决方案非常简单。
import java.util.*;
public class Recursion {
static void sum(int[] arr, int i, int sum, int target, String s)
{
for(int j = i+1; j<arr.length; j++){
if(sum+arr[j] == target){
System.out.println(s+" "+String.valueOf(arr[j]));
}else{
sum(arr, j, sum+arr[j], target, s+" "+String.valueOf(arr[j]));
}
}
}
public static void main(String[] args)
{
int[] numbers = {6,3,8,10,1};
for(int i =0; i<numbers.length; i++){
sum(numbers, i, numbers[i], 18, String.valueOf(numbers[i]));
}
}
}
- Townim Faisal
5
这是我的Ruby程序。它将返回一个数组，其中每个元素都是满足提供的目标值的子序列的总和。
array = [1, 3, 4, 2, 7, 8, 9]
0..array.size.times.each do |i|
array.combination(i).to_a.each { |a| print a if a.inject(:+) == 9}
end
- Ritesh Ranjan
2
这不会是O(2^n)吗？ - Ignacio Tartavull
@IgnacioTartavull 这个问题是NP完全问题，[SP13] 来自 Garey 和 Johnson：子集和问题。这意味着我们不知道如何以比指数更好的确定性实现这个问题。然而，这个问题也是伪多项式问题。这意味着，如果你限制了你要寻找的总和，例如 9，并将其视为常数，则可以在多项式时间内解决这个问题。事实上，这就是所选答案所做的：它在子例程中的第一行分配一个 sum+1 的数组。但是，如果
sum 是 64K 而 array 只有几个项，那么这个解决方案将击败其他方案。 - rocky4
针对大量输入（即25到30个）的情况，这里有一种高效的解决方案：
我通过两种方式提高了效率：
- 利用了一个简单的滚轮概念，通过所有可能的迭代进行二进制计数，而不是使用基本转换语言特性的数学昂贵方法。这个“滚轮”类似于旧式机械计数器或里程表。直到我们超过二进制数字的数量（例如，我们集合中的数字计数）为止，它会递归地向前滚动尽可能多的位置。
- 主要收益来自于不需要每次求和整个候选集。相反，它维护一个运行总和，每次“滚动滚轮”时，仅调整最后一个候选集与之前相比已经改变的部分的运行总和。这可以节省很多计算，因为大多数“滚轮滚动”只会改变一个或两个数字。
此解决方案适用于负数、十进制金额和重复的输入值。由于大多数语言中浮点小数运算的奇怪方式，您应该将输入集保留在几个小数位数以内，否则可能会产生一些不可预测的行为。
在我旧的2012年桌面电脑上，给定的代码在javascript/node.js中处理25个输入值需要约0.8秒，在C#中需要3.4秒。
javascript
let numbers = [-0.47, -0.35, -0.19, 0.23, 0.36, 0.47, 0.51, 0.59, 0.63, 0.79, 0.85,
0.91, 0.99, 1.02, 1.17, 1.25, 1.39, 1.44, 1.59, 1.60, 1.79, 1.88, 1.99, 2.14, 2.31];
let target = 24.16;
displaySubsetsThatSumTo(target, numbers);
function displaySubsetsThatSumTo(target, numbers)
{
let wheel = [0];
let resultsCount = 0;
let sum = 0;
const start = new Date();
do {
sum = incrementWheel(0, sum, numbers, wheel);
//Use subtraction comparison due to javascript float imprecision
if (sum != null && Math.abs(target - sum) < 0.000001) {
//Found a subset. Display the result.
console.log(numbers.filter(function(num, index) {
return wheel[index] === 1;
}).join(' + ') + ' = ' + target);
resultsCount++;
}
} while (sum != null);
const end = new Date();
console.log('--------------------------');
console.log(`Processed ${numbers.length} numbers in ${(end - start) / 1000} seconds (${resultsCount} results)`);
}
function incrementWheel(position, sum, numbers, wheel) {
if (position === numbers.length || sum === null) {
return null;
}
wheel[position]++;
if (wheel[position] === 2) {
wheel[position] = 0;
sum -= numbers[position];
if (wheel.length < position + 2) {
wheel.push(0);
}
sum = incrementWheel(position + 1, sum, numbers, wheel);
}
else {
sum += numbers[position];
}
return sum;
}
-----------------------------------------------------------------
Alternate, more efficient version using Gray Code binary counting
technique as suggested in comment
-----------------------------------------------------------------
const numbers = [-0.47, -0.35, -0.19, 0.23, 0.36, 0.47, 0.51,
0.59, 0.63, 0.79, 0.85, 0.91, 0.99, 1.02, 1.17, 1.25,
1.39, 1.44, 1.59, 1.60, 1.79, 1.88, 1.99, 2.14, 2.31];
const target = 24.16;
displaySubsetsThatSumTo(target, numbers);
function displaySubsetsThatSumTo(target, numbers)
{
let resultsCount = 0;
let sum = 0;
let wheel = []; //binary counter
let changeEvery = []; //how often each binary digit flips
let nextChange = []; //when each binary digit will next flip
for(let i = 0; i < numbers.length; i++) {
//Initialize wheel and wheel-update data. Using Gray Code binary counting technique,
// whereby only one binary digit in the wheel changes on each iteration. Then only
// a single sum operation is required each iteration.
wheel.push(0);
changeEvery.push(2 ** (numbers.length - i));
nextChange.push(2 ** (numbers.length - i - 1));
}
const start = new Date();
const numIterations = 2 ** numbers.length;
for (counter = 1; counter < numIterations; counter++) {
for (let i = nextChange.length - 1; i >= 0; i--) {
if(nextChange[i] === counter) {
nextChange[i] += changeEvery[i];
if (wheel[i] === 1) {
wheel[i] = 0;
sum -= numbers[i];
}
else {
wheel[i] = 1;
sum += numbers[i];
}
break;
}
}
//Use subtraction comparison due to javascript float imprecision
if (Math.abs(target - sum) < 0.000001) {
//Found a subset. Display the result.
console.log(numbers.filter((num, index) => wheel[index] === 1)
.join(' + ') + ' = ' + target);
resultsCount++;
}
}
const end = new Date();
console.log('--------------------------');
console.log(`Processed ${numbers.length} numbers in ${(end - start) / 1000} seconds (${resultsCount} results)`);
}
C#
public class Program
{
static void Main(string[] args)
{
double[] numbers = { -0.47, -0.35, -0.19, 0.23, 0.36, 0.47, 0.51, 0.59, 0.63, 0.79, 0.85,
0.91, 0.99, 1.02, 1.17, 1.25, 1.39, 1.44, 1.59, 1.60, 1.79, 1.88, 1.99, 2.14, 2.31 };
double target = 24.16;
DisplaySubsetsThatSumTo(target, numbers);
}
private static void DisplaySubsetsThatSumTo(double Target, double[] numbers)
{
var stopwatch = new System.Diagnostics.Stopwatch();
bool[] wheel = new bool[numbers.Length];
int resultsCount = 0;
double? sum = 0;
stopwatch.Start();
do
{
sum = IncrementWheel(0, sum, numbers, wheel);
//Use subtraction comparison due to double type imprecision
if (sum.HasValue && Math.Abs(sum.Value - Target) < 0.000001F)
{
//Found a subset. Display the result.
Console.WriteLine(string.Join(" + ", numbers.Where((n, idx) => wheel[idx])) + " = " + Target);
resultsCount++;
}
} while (sum != null);
stopwatch.Stop();
Console.WriteLine("--------------------------");
Console.WriteLine($"Processed {numbers.Length} numbers in {stopwatch.ElapsedMilliseconds / 1000.0} seconds ({resultsCount} results). Press any key to exit.");
Console.ReadKey();
}
private static double? IncrementWheel(int Position, double? Sum, double[] numbers, bool[] wheel)
{
if (Position == numbers.Length || !Sum.HasValue)
{
return null;
}
wheel[Position] = !wheel[Position];
if (!wheel[Position])
{
Sum -= numbers[Position];
Sum = IncrementWheel(Position + 1, Sum, numbers, wheel);
}
else
{
Sum += numbers[Position];
}
return Sum;
}
}
输出
-0.35 + 0.23 + 0.36 + 0.47 + 0.51 + 0.59 + 0.63 + 0.79 + 0.85 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
0.23 + 0.51 + 0.59 + 0.63 + 0.79 + 0.85 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
-0.47 + 0.23 + 0.47 + 0.51 + 0.59 + 0.63 + 0.79 + 0.85 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
-0.19 + 0.36 + 0.51 + 0.59 + 0.63 + 0.79 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
-0.47 + -0.19 + 0.36 + 0.47 + 0.51 + 0.59 + 0.63 + 0.79 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
0.23 + 0.47 + 0.51 + 0.63 + 0.85 + 0.91 + 0.99 + 1.02 + 1.17 + 1.25 + 1.39 + 1.44 + 1.59 + 1.6 + 1.79 + 1.88 + 1.99 + 2.14 + 2.31 = 24.16
--------------------------
Processed 25 numbers in 0.823 seconds (6 results)
- CooManCoo
2
今天看到了你的解决方案——很酷。如果你以这样的方式遍历轮子，只有一个数字会改变，那么你可以进一步优化。这将与对[数字]维超立方体进行哈密顿遍历相同。例如，对于3D：000、001、011、010、110、100、101、111。每次迭代只有一个数字会改变。希望你会觉得这很有趣 :) —— 这个名字叫做“格雷码”，在维基上查一下吧。 - JS_Riddler
@JS_Riddler 真的很有趣。我在 JavaScript 代码块的末尾添加了一个替代版本，使用了 Gray Code 技术。测试各种输入集，性能提高了50%到70%! - CooManCoo
2
这是我的JS动态规划实现。它将返回一个数组，其中每个子数组都包含总和为提供的目标值的子序列。
function getSummingItems(a,t){
return a.reduce((h,n) => Object.keys(h)
.reduceRight((m,k) => +k+n <= t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n)))
: m[k].map(sa => sa.concat(n)),m)
: m, h), {0:[[]]})[t];
}
var arr = Array(20).fill().map((_,i) => i+1), // [1,2,..,20]
tgt = 42,
res = [];
console.time("test");
res = getSummingItems(arr,tgt);
console.timeEnd("test");
console.log("found",res.length,"subsequences summing to",tgt);
console.log(JSON.stringify(res));- Redu
2
这个问题通常可以使用动态规划（DP）的解决方案。
你可以进行一项优化，即记录特定总和的解决方案数量，而不是实际构成该总和的集合...
- Kshitij Banerjee
1
RUBY
这段代码将拒绝空数组并返回具有值的正确数组。
def find_sequence(val, num)
b = val.length
(0..b - 1).map {|n| val.uniq.combination(n).each.find_all {|value| value.reduce(:+) == num}}.reject(&:empty?)
end
val = [-10, 1, -1, 2, 0]
num = 2
输出将会是[[2]，[2,0]，[-1,1,2]，[-1,1,2,0]]
- Preethi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接