给定一组数字：{1, 3, 2, 5, 4, 9}，找出总和为特定值的子集的数量（例如，本例中的 9）。
这类似于子集总和问题，但略有不同的是，我们不必检查集合是否有总和为 9 的子集，而是必须找到这样的子集的数量。我在 这里关注子集和问题的解决方案。但是我想知道如何修改它以返回子集的计数。
问问题
130080 次
18 回答
36
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)
解释
这是经典问题之一。这个想法是找到当前数字的可能总和的数量。确实，只有一种方法可以使总和为 0。一开始，我们只有一个数字。我们从目标（解决方案中的变量最大值）开始并减去该数字。如果有可能得到那个数字的总和（对应于那个数字的数组元素不为零），那么将它添加到对应于当前数字的数组元素中。通过这种方式，程序会更容易理解
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、3 - 2 为 1 并且数组元素对应1是1，我们把它添加到3的数组元素中
[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。
于 2013-08-19T11:51:02.827 回答
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 类型。
算法仅适用于正数。
于 2013-08-19T06:56:36.313 回答
12
这是一个Java Solution：
这是一个经典的反向跟踪问题，用于查找作为输入的整数数组或集合的所有可能子集，然后filtering是那些总和为 e的子集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 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++;
}
}
}
它给出了总和为目标的子集的空格分隔值。
将打印出总和为25in
的子集的逗号分隔值{24, 1, 15, 3, 4, 15, 3}
1) 24 1
2) 3 4 15 3
3) 15 3 4 3
于 2015-05-13T17:53:22.023 回答
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]));
}
}
}
于 2017-05-09T06:23:34.417 回答
6
同一站点 geeksforgeeks 还讨论了输出总和为特定值的所有子集的解决方案：http ://www.geeksforgeeks.org/backttracking-set-4-subset-sum/
在您的情况下，您只需要计算它们，而不是输出集。请务必检查同一页面中的优化版本，因为它是一个NP 完全问题。
这个问题之前在stackoverflow中也被问过和回答过，但没有提到这是一个子集和问题： Finding all possible combination of numbers to reach a given sum
于 2013-08-19T03:48:04.233 回答
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
于 2017-05-03T13:09:47.850 回答
4
当有大量输入（即 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)
于 2019-04-21T03:07:36.527 回答
2
通常的 DP 解决方案适用于该问题。
您可能会做的一项优化是计算特定总和存在多少解决方案，而不是构成该总和的实际集合......
于 2013-08-19T08:43:04.950 回答
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));于 2017-04-07T08:31:45.820 回答
1
红宝石
此代码将拒绝空数组并返回带有值的正确数组。
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]]
于 2018-04-09T12:51:52.783 回答
0
子集和问题可以使用动态规划在O(sum*n)中解决。子集和的最优子结构如下：
SubsetSum(A, n, sum) = SubsetSum(A, n-1, sum) || SubsetSum(A, n-1, sum-set[n-1])
SubsetSum(A, n, sum) = 0，如果 sum > 0 并且 n == 0 SubsetSum(A, n, sum) = 1，如果 sum == 0
这里A是元素数组，n是数组A的元素数，sum是子集中元素的总和。
使用此 dp，您可以求解总和的子集数。
为了获取子集元素，我们可以使用以下算法：
通过调用 SubsetSum(A, n, sum)填充dp[n][sum]后，我们从 dp[n][sum] 递归遍历它。对于遍历的单元格，我们在到达之前存储路径并考虑元素的两种可能性。
1) 元素包含在当前路径中。
2) 元素不包含在当前路径中。
每当 sum 变为 0 时，我们就会停止递归调用并打印当前路径。
void findAllSubsets(int dp[], int A[], int i, int sum, vector<int>& p) {
if (sum == 0) {
print(p);
return;
}
// If sum can be formed without including current element
if (dp[i-1][sum])
{
// Create a new vector to store new subset
vector<int> b = p;
findAllSubsets(dp, A, i-1, sum, b);
}
// If given sum can be formed after including
// current element.
if (sum >= A[i] && dp[i-1][sum-A[i]])
{
p.push_back(A[i]);
findAllSubsets(dp, A, i-1, sum-A[i], p);
}
}
于 2018-11-02T14:14:49.613 回答
0
以下解决方案还提供了提供特定总和的子集数组（这里总和 = 9）
array = [1, 3, 4, 2, 7, 8, 9]
(0..array.size).map { |i| array.combination(i).to_a.select { |a| a.sum == 9 } }.flatten(1)
返回返回总和为 9 的子集数组
=> [[9], [1, 8], [2, 7], [3, 4, 2]]
于 2018-12-08T05:02:53.513 回答
0
虽然很容易找到它们是否是目标总和的子集，但当您需要跟踪正在考虑的部分子集时，实现会变得很棘手。
如果您使用链表、散列集或任何其他通用集合，您会很想在包含该项目的调用之前将一个项目添加到此集合中，然后在排除该项目的调用之前将其删除。这不会按预期工作，因为将发生添加的堆栈帧与将发生删除的堆栈帧不同。
解决方案是使用字符串来跟踪序列。附加到字符串可以在函数调用中内联完成；从而保持相同的堆栈帧，然后您的答案将完美地符合原始的 hasSubSetSum 递归结构。
import java.util.ArrayList;
公共类解决方案{
public static boolean hasSubSet(int [] A, int target) {
ArrayList<String> subsets = new ArrayList<>();
helper(A, target, 0, 0, subsets, "");
// Printing the contents of subsets is straightforward
return !subsets.isEmpty();
}
private static void helper(int[] A, int target, int sumSoFar, int i, ArrayList<String> subsets, String curr) {
if(i == A.length) {
if(sumSoFar == target) {
subsets.add(curr);
}
return;
}
helper(A, target, sumSoFar, i+1, subsets, curr);
helper(A, target, sumSoFar + A[i], i+1, subsets, curr + A[i]);
}
public static void main(String [] args) {
System.out.println(hasSubSet(new int[] {1,2,4,5,6}, 8));
}
}
于 2018-06-22T09:27:53.437 回答
0
public class SumOfSubSet {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {1,2};
int sum=0;
if(a.length<=0) {
System.out.println(sum);
}else {
for(int i=0;i<a.length;i++) {
sum=sum+a[i];
for(int j=i+1;j<a.length;j++) {
sum=sum+a[i]+a[j];
}
}
System.out.println(sum);
}
}
}
于 2017-12-20T18:28:43.943 回答
0
我的回溯解决方案：- 对数组进行排序，然后应用回溯。
void _find(int arr[],int end,vector<int> &v,int start,int target){
if(target==0){
for(int i = 0;i<v.size();i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
else{
for(int i = start;i<=end && target >= arr[i];i++){
v.push_back(arr[i]);
_find(arr,end,v,i+1,target-arr[i]);
v.pop_back();
}
}
}
于 2018-04-22T03:57:21.647 回答
0
I used Dynamic Programming & Memoization to find count of subsets from a set having a particular total. The code below code is in java. Have included the comments to explain the code intentions -
package com.company.dynamicProgramming;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
public class FindSumInSubSet {
public static void main(String...args){
int[] arr = {3, 2, 4, 6, 10};
int total = 16;
// Challenge is to find the subsets of numbers total 6 in above super set (represented as array)
// In general - Write a code to count subset of elements totalling m(6 above) in given set of n(9 as array size above) elements
Map<Entry, Integer> memoMap = new HashMap<>();
Entry entry = new Entry(total, arr.length-1);
int count = countSubSetForSum(arr, entry, memoMap);
System.out.format("In set of %d elements, the number of subsets having total=%d is %d %n", arr.length,total, count);
}
static int countSubSetForSum(int[] arr, Entry entry, Map<Entry, Integer> memoMap){
int total = entry.getTotal();
int i = entry.getI();
if (total == 0){ // means element was equal in previous recursion
return 1;
}else if(total < 0){ // means element was less in previous recursion i.e. not equal
return 0;
}else if (i < 0){ // means arr was finished previous recursion
return 0;
}else if (arr[i] > total){ // means element is greater than total
// i.e. leave that element and look further sets excluding this element
return getCountForIthAndTotal(arr, new Entry( total, i-1), memoMap);
}else{ // means element is less than total i.e. 2 possibilities :
// 1st - look further sets including this element
// 2nd - look further sets excluding this element
return getCountForIthAndTotal(arr, new Entry( total-arr[i], i-1), memoMap) +
getCountForIthAndTotal(arr, new Entry( total, i-1), memoMap);
}
}
static int getCountForIthAndTotal(int[] arr, Entry entry, Map<Entry, Integer> memoMap){
if (memoMap.containsKey(entry)){ //look up in has table if we already calculated particular total for ith subset..
return memoMap.get(entry); //This is nothing but using memoization that reduce the entire below code i.e. further recursion -
}else {
int count = countSubSetForSum(arr, entry, memoMap); //Recursion
memoMap.put(entry, count); //Build memoization
return count;
}
}
//Just Data Structure for Key in HashMap (memoMaP)... intent to include particular total for ith element's subset.
static class Entry {
int total;
int i;
public Entry(int total, int i) {
this.total = total;
this.i = i;
}
public int getTotal() {
return total;
}
public int getI() {
return i;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Entry entry = (Entry) o;
return total == entry.total &&
i == entry.i;
}
@Override
public int hashCode() {
return Objects.hash(total, i);
}
}
}
When i ran this the out put is :
In set of 5 elements, the number of subsets having total=16 is 2
Process finished with exit code 0
于 2020-03-26T09:16:57.853 回答
0
返回列表子集的Python 函数子集，该子集加起来为特定值
def subset(ln, tar):#ln=Lenght Of String, tar= Target
s=[ int(input('Insert Numeric Value Into List:')) for i in range(ln) ]#Inserting int Values in s of type<list>
if sum(s) < tar:#Sum of List is less than Target Value
return
elif sum(s) == tar:#Sum of list is equal to Target Value i.e for all values combinations
return s
elif tar in s:#Target value present in List i.e for single value
return s[s.index(tar)]
else:#For remaining possibilities i.e for all except( single and all values combinations )
from itertools import combinations# To check all combinations ==> itertools.combinations(list,r) OR return list of all subsets of length r
r=[i+1 for i in range(1,ln-1)]# Taking r as only remaining value combinations, i.e.
# Except( r=1 => for single value combinations AND r=length(list) || r=ln => For all value combinations
lst=list()#For Storing all remaining combinations
for i in range(len(r)):
lst.extend(list( combinations(s,r[i]) ))
for i in range(len(lst)):# To check remaining possibilities
if tar == sum(lst[i]):
return list(lst[i])
子集（int（输入（'列表长度：'）），int（输入（'目标：'）））
于 2020-07-26T06:54:03.973 回答
0
我发现很多面试都要求这样做，所以我实施了一个非常简单易懂的解决方案。首先，我生成所有可能的组合，然后你可以做任何你想做的事情。看一下这个：
public static void main(String[] args) {
int[] numbers = new int[]{1, 2, 3, 4, 5};
List<int[]> allPossibleCombinatiosForNumbers = new ArrayList<>();
for (int i = 2; i < numbers.length; i++) {
allPossibleCombinatiosForNumbers.addAll(getCombinationsOfNElements(numbers, i));
}
for (int[] combination : allPossibleCombinatiosForNumbers) {
printArray(combination);
printArrayIfNumbersSumExpectedValue(combination, 6);
}
}
private static List<int[]> getCombinationsOfNElements(int[] numbers, int n) {
int elementsKnown = n - 1;
List<int[]> allCombinationsOfNElements = new ArrayList<>();
for (int i = 0; i < numbers.length - elementsKnown; i++) {
int[] combination = new int[n];
for (int j = 0; j < n; j++) {
combination[j] = numbers[i + j];
}
allCombinationsOfNElements.addAll(generationCombinations(combination, i + elementsKnown, numbers));
}
return allCombinationsOfNElements;
}
private static List<int[]> generationCombinations(int[] knownElements, int index, int[] numbers) {
List<int[]> combinations = new ArrayList<>();
for (int i = index; i < numbers.length; i++) {
int[] combinationComplete = Arrays.copyOf(knownElements, knownElements.length);
combinationComplete[knownElements.length - 1] = numbers[i];
combinations.add(combinationComplete);
}
return combinations;
}
private static void printArray(int[] numbers) {
System.out.println();
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + " ");
}
}
private static void printArrayIfNumbersSumExpectedValue(int[] numbers, int expectedValue) {
int total = 0;
for (int i = 0; i < numbers.length; i++) {
total += numbers[i];
}
if (total == expectedValue) {
System.out.print("\n ----- Here is a combination you are looking for -----");
printArray(numbers);
System.out.print("\n -------------------------------");
}
}
于 2020-06-18T02:16:56.077 回答