给定一组数字:{1,3,2,5,4,9},找到总和为特定值(例如此示例中的9)的子集数量。
这类似于子集总和问题,但稍有不同的是,我们要找到这样的子集数量,而不是检查集合是否有总和为9的子集。我正在遵循这里子集总和问题的解决方案。但我想知道如何修改它以返回子集的数量。
给定一组数字:{1,3,2,5,4,9},找到总和为特定值(例如此示例中的9)的子集数量。
这类似于子集总和问题,但稍有不同的是,我们要找到这样的子集数量,而不是检查集合是否有总和为9的子集。我正在遵循这里子集总和问题的解决方案。但我想知道如何修改它以返回子集的数量。
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(1-1变成0,对应0的元素为1)。所以数组会是这样(请注意,元素0将会是1)。[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。
Numbers
变量包含实际使用的输入。 - thefourtheye你可以使用动态规划。算法复杂度为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类型的范围。
该算法仅适用于正数。
这里是一个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
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]));
}
}
}
这是我的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
sum
是 64K 而 array
只有几个项,那么这个解决方案将击败其他方案。 - rocky针对大量输入(即25到30个)的情况,这里有一种高效的解决方案:
我通过两种方式提高了效率:
此解决方案适用于负数、十进制金额和重复的输入值。由于大多数语言中浮点小数运算的奇怪方式,您应该将输入集保留在几个小数位数以内,否则可能会产生一些不可预测的行为。
在我旧的2012年桌面电脑上,给定的代码在javascript/node.js中处理25个输入值需要约0.8秒,在C#中需要3.4秒。
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)`);
}
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)
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));
这个问题通常可以使用动态规划(DP)的解决方案。
你可以进行一项优化,即记录特定总和的解决方案数量,而不是实际构成该总和的集合...
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]]