给定的整数集合的子集，其总和为常数N：Java [英] Subsets of a given Set of Integers whose sum is a Constant N : Java

问题描述

给定一组整数，如何找到与给定值相加的子集...子集问题？

Given a set of integers, how to find a subset that sums to a given value...the subset problem ?

示例：S = {1,2 ，4,3,2,5}和n = 7
查找总和为n的可能子集。
我试图google出来找到很多链接，但不清楚。
我们如何在java中解决这个问题，什么是要使用的数据结构及其复杂性？

Example : S = {1,2,4,3,2,5} and n= 7 Finding the possible subsets whose sum is n. I tried to google out found many links,but were not clear. How can we solve this in java and what is the data structure to be used and its complexity ?

推荐答案

不要给你任何代码，但是解释它是如何工作的。

I wont give you any code, but explain how it works.

1. 从 0运行一个循环到（2 ^ k -1）


2. 对于1中的每个值，其二进制表示中的1表示此值被选择，否则为0。


3. 测试以查看所选数字的总和是否等于 n 。

1. Run a loop from 0 to (2^k-1)
2. For each value in 1, a 1 in its binary representation indicates that this value is chosen and 0 otherwise.
3. Test to see if the sum of chosen numbers is equal to n.

以上方法将评估给定集合的每个可能子集。

The above method will evaluate each possible subset of the given set.

如果值的上限较小，则可以使用动态编程方法。

If the upper limit of the values is small, then Dynamic Programming Approach could be used.

这篇关于给定的整数集合的子集，其总和为常数N：Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！