find总和为特定值的所有子集
给定一组数字：{1,3,2,5,4,9}，求出总和为一个特定值的子集数（例如，在这个例子中为9）。
这与子集和问题类似，只是略有不同，不是检查集合是否具有总和为9的子集，我们必须find这样的子集的数量。 我在这里遵循子集总和问题的解决scheme。 但是，我想知道如何修改它以返回子集计数。
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) 说明
这是经典问题之一。 这个想法是找出当前数字的可能和数。 而且它的确是有一个办法可以使得和为零。一开始我们只有一个数字。 我们从我们的目标开始（解决scheme中的最大variables）并减去该数字。 如果可以得到该数字的和（与该数字相对应的数组元素不为零），则将其添加到与当前数字对应的数组元素中。 这个程序会更容易理解
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）。 所以数组会是这样的（记住元素零将有1）
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
现在，第二个数字是2.我们从9开始减去2并且它是无效的（因为7的数组元素是零，我们跳过这个），我们继续这样做直到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。
您可以使用dynamic编程。 algorithm复杂度为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的值，容易溢出inttypes。
Algo只能用于正数。
这是一个Java Solution ：
这是一个经典的回溯问题，用于查找整数数组的所有可能的子集或设置input，然后filtering那些和给定target
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 up 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} 24,1，15，3，4，15，3}中总和为25的子集的共同分隔值
1）24 1
2）3 4 15 3
3）15 3 4 3
同样的网站geeksforgeeks也讨论了解决scheme输出所有的子集总和为一个特定的值： http : //www.geeksforgeeks.org/backttracking-set-4-subset-sum/
在你的情况下，而不是输出集，你只需要数它们。 一定要检查在同一页面的优化版本，因为这是一个NP完整的问题。
这个问题也被问及并在stackoverflow之前回答，没有提到它是一个子集和问题： find所有可能的数字组合，以达到给定的总和
这是我的ruby程序。 它将返回数组，每个数组都保持子序列总计到提供的目标值。
array = [1, 3, 4, 2, 7, 8, 9] 0..array.size.times.each do |i| @ary.combination(i).to_a.each { |a| print a if a.inject(:+) == 9} end
我已经通过java解决了这个问题。 这个解决scheme很简单。
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])); } } }
通常的DP解决scheme对于这个问题是正确的。
你可以做的一个优化就是保留一个特定的总和有多less个解决scheme，而不是构成这个总和的实际集合。
这是我在JS中的dynamic编程实现。 它将返回一个数组数组，每个数组都保持子序列总和为所提供的目标值。
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));
