给定的整数集合的子集，其总和为常数N：Java

本文介绍了给定的整数集合的子集，其总和为常数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.

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

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

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

Run a loop from 0 to (2^k-1)

For each value in 1, a 1 in its binary representation indicates that this value is chosen and 0 otherwise.

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.