例如，如果 A = {10, 20, 30, 40, ..., 200}，则 {10, 20, 30, 40, 100} 和 {90, 110} 是具有相同值的两个子集总和(即 200)。
既然输入的长度只有20？我们不能简单地生成数字的所有组合，计算它们的总和，将它们存储在 HashMap [key = sum, value = count] 中，并迭代映射条目以查看总和是否被多次计算？
最佳答案
经过一些实验后，我说服自己简单地计算所有 2^n 的和并存储它们是最好的方法。然而，实现一个小集合的效率对于避免这些 O(2^n*n) 的总和的计算花费太长时间是至关重要的。
我已经使用整数 0 到 2^n-1 来表示所有子集的集合(powerset)。
public class Sum {
private Map<Integer,List<Integer>> sum2sets = new HashMap<>();
private int n;
private int max;
private int[] theSet;
public Sum( int[] theSet ){
this.theSet = theSet;
int n = theSet.length;
max = (1 << n) - 1;
int maxSum = n*(n+1)/2;
}
因此，可以用循环计算总和
private int sum( int n ){
int s = 0;
for( int i = 0; n > 0; i++ ){
if( (n & 1) != 0 ) s += theSet[i];
n = n >> 1;
}
return s;
}
计算所有子集的总和很简单:
public void buildLists(){
int maxlen = 0;
int maxsum = 0;
for( int i = 0; i <= max; i++ ){
int s = sum( i );
List<Integer> set = sum2sets.get( s );
if( set == null ){
set = new ArrayList<Integer>();
sum2sets.put( s, set );
}
set.add( i );
int len = sum2sets.size();
if( len > maxlen ){
maxsum = s;
maxlen = len;
}
}
System.out.println( "max. len " + maxlen + " at " + maxsum );
}
和相等的集合的结果集不同。连续的整数 1、2、... 20 将产生一长串产生特定总和的集合，例如对于总和 105，有 15272 组。
选择:3、7、13、18、21、22、30、34、42、49、50、61、65、67、70、71、88、91、93、99 有最大数量总和 994 的集合等于 963。
这张 map 的进一步处理取决于 OP 真正想要什么——评论中有一些问题。
例如，您可以找到总和相同的子集对，无论是否不相交，但这些数字将非常大。
public String setAsString( int n ){
StringBuilder sb = new StringBuilder( "[" );
String del = "";
for( int i = 0; n > 0; i++ ){
if( (n & 1) != 0 ){
sb.append( del ).append( theSet[i] );
del = ", ";
}
n = n >> 1;
}
sb.append( "]" );
return sb.toString();
}
public void dumpAll( int n ){
for( Map.Entry<Integer,List<Integer>> e: sum2sets.entrySet() ){
int sum = e.getKey();
List<Integer> sets = e.getValue();
if( sets.size() >= 2 ){
System.out.println( "sum: " + sum );
for( Integer i: sets ){
System.out.print( " " + setAsString( i ) );
}
System.out.println();
if( --n == 0 ) break;
}
}
}
这是运行示例的主要方法。
public static void main( String[] args ){
int[] nums = new int[]{
3, 7, 13, 18, 21, 22, 30, 34, 42, 49,
50, 61, 65, 67, 70, 71, 88, 91, 93, 99 };
Sum sum = new Sum( nums );
sum.buildLists();
sum.dumpAll( 50 );
}
以及出色的输出(只是一小部分):
max. len 963 at 994
sum: 21
[3, 18] [21]
sum: 25
[7, 18] [3, 22]
sum: 28
[3, 7, 18] [7, 21]
sum: 31
[13, 18] [3, 7, 21]
sum: 34
[3, 13, 18] [13, 21] [34]
sum: 37
[3, 13, 21] [7, 30] [3, 34]
sum: 38
[7, 13, 18] [3, 13, 22]
sum: 40
[18, 22] [3, 7, 30]
sum: 41
[3, 7, 13, 18] [7, 13, 21] [7, 34]
sum: 42
[3, 18, 21] [7, 13, 22] [42]
sum: 43
[3, 18, 22] [21, 22] [13, 30]
sum: 44
[3, 7, 13, 21] [3, 7, 34]
sum: 45
[3, 7, 13, 22] [3, 42]
sum: 46
[7, 18, 21] [3, 21, 22] [3, 13, 30]
sum: 47
[7, 18, 22] [13, 34]
sum: 49
[3, 7, 18, 21] [7, 42] [49]
sum: 50
[3, 7, 18, 22] [7, 21, 22] [7, 13, 30] [3, 13, 34] [50]
sum: 51
[3, 18, 30] [21, 30]
sum: 52
[13, 18, 21] [22, 30] [18, 34] [3, 7, 42] [3, 49]
sum: 53
[13, 18, 22] [3, 7, 21, 22] [3, 7, 13, 30] [3, 50]
sum: 54
[3, 21, 30] [7, 13, 34]
sum: 55
[3, 13, 18, 21] [7, 18, 30] [3, 22, 30] [3, 18, 34] [21, 34] [13, 42]
sum: 56
[3, 13, 18, 22] [13, 21, 22] [22, 34] [7, 49]
sum: 57
[3, 7, 13, 34] [7, 50]
sum: 58
[3, 7, 18, 30] [7, 21, 30] [3, 21, 34] [3, 13, 42]
sum: 59
[7, 13, 18, 21] [3, 13, 21, 22] [7, 22, 30] [7, 18, 34] [3, 22, 34] [3, 7, 49]
sum: 60
[7, 13, 18, 22] [18, 42] [3, 7, 50]
sum: 61
[18, 21, 22] [13, 18, 30] [3, 7, 21, 30] [61]
sum: 62
[3, 7, 13, 18, 21] [3, 7, 22, 30] [3, 7, 18, 34] [7, 21, 34] [7, 13, 42] [13, 49]
sum: 63
[3, 7, 13, 18, 22] [7, 13, 21, 22] [7, 22, 34] [3, 18, 42] [21, 42] [13, 50]
sum: 64
[3, 18, 21, 22] [3, 13, 18, 30] [13, 21, 30] [30, 34] [22, 42] [3, 61]
sum: 65
[13, 22, 30] [13, 18, 34] [3, 7, 21, 34] [3, 7, 13, 42] [3, 13, 49] [65]
sum: 66
[3, 7, 13, 21, 22] [3, 7, 22, 34] [3, 21, 42] [3, 13, 50]
sum: 67
[3, 13, 21, 30] [3, 30, 34] [7, 18, 42] [3, 22, 42] [18, 49] [67]
sum: 68
[7, 18, 21, 22] [7, 13, 18, 30] [3, 13, 22, 30] [3, 13, 18, 34] [13, 21, 34] [18, 50] [7, 61] [3, 65]
sum: 69
[18, 21, 30] [13, 22, 34] [7, 13, 49]
sum: 70
[18, 22, 30] [3, 7, 18, 42] [7, 21, 42] [3, 18, 49] [21, 49] [7, 13, 50] [3, 67] [70]
sum: 71
[3, 7, 18, 21, 22] [3, 7, 13, 18, 30] [7, 13, 21, 30] [3, 13, 21, 34] [7, 30, 34] [7, 22, 42] [22, 49] [3, 18, 50] [21, 50] [3, 7, 61] [71]
sum: 72
[3, 18, 21, 30] [7, 13, 22, 30] [7, 13, 18, 34] [3, 13, 22, 34] [30, 42] [3, 7, 13, 49] [22, 50] [7, 65]
sum: 73
[3, 18, 22, 30] [21, 22, 30] [18, 21, 34] [13, 18, 42] [3, 7, 21, 42] [3, 21, 49] [3, 7, 13, 50] [3, 70]
sum: 74
[13, 18, 21, 22] [3, 7, 13, 21, 30] [18, 22, 34] [3, 7, 30, 34] [3, 7, 22, 42] [7, 18, 49] [3, 22, 49] [3, 21, 50] [13, 61] [7, 67] [3, 71]
sum: 75
[3, 7, 13, 22, 30] [3, 7, 13, 18, 34] [7, 13, 21, 34] [3, 30, 42] [7, 18, 50] [3, 22, 50] [3, 7, 65]
sum: 76
[7, 18, 21, 30] [3, 21, 22, 30] [3, 18, 21, 34] [7, 13, 22, 34] [3, 13, 18, 42] [13, 21, 42] [34, 42]
sum: 77
[3, 13, 18, 21, 22] [7, 18, 22, 30] [3, 18, 22, 34] [21, 22, 34] [13, 30, 34] [13, 22, 42] [3, 7, 18, 49] [7, 21, 49] [3, 13, 61] [3, 7, 67] [7, 70]
sum: 78
[3, 7, 13, 21, 34] [7, 22, 49] [3, 7, 18, 50] [7, 21, 50] [13, 65] [7, 71]
sum: 79
[3, 7, 18, 21, 30] [3, 7, 13, 22, 34] [3, 13, 21, 42] [7, 30, 42] [3, 34, 42] [30, 49] [7, 22, 50] [18, 61]
sum: 80
[3, 7, 18, 22, 30] [7, 21, 22, 30] [7, 18, 21, 34] [3, 21, 22, 34] [3, 13, 30, 34] [7, 13, 18, 42] [3, 13, 22, 42] [13, 18, 49] [3, 7, 21, 49] [30, 50] [13, 67] [3, 7, 70]
sum: 81
[7, 13, 18, 21, 22] [7, 18, 22, 34] [18, 21, 42] [3, 7, 22, 49] [13, 18, 50] [3, 7, 21, 50] [7, 13, 61] [3, 13, 65] [3, 7, 71]
sum: 82
[13, 18, 21, 30] [18, 30, 34] [18, 22, 42] [3, 7, 30, 42] [3, 30, 49] [3, 7, 22, 50] [3, 18, 61] [21, 61]
sum: 83
[13, 18, 22, 30] [3, 7, 21, 22, 30] [3, 7, 18, 21, 34] [3, 7, 13, 18, 42] [7, 13, 21, 42] [7, 34, 42] [3, 13, 18, 49] [13, 21, 49] [34, 49] [3, 30, 50] [22, 61] [18, 65] [3, 13, 67] [13, 70]
关于algorithm - 给定一组 20 个不同的正整数，找到两个具有相同总和的子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24855365/