例如，如果 A = {10, 20, 30, 40, ..., 200}，则 {10, 20, 30, 40, 100} 和 {90, 110} 是两个具有相同和的子集（其中是 200）。
由于输入的长度只有20？我们不能简单地生成数字的所有组合，计算它们的总和，将它们存储在哈希映射中 [key = sum, value = count] 并在映射条目的迭代中查看总和是否已被多次计算?
问问题
1535 次
1 回答
1
在进行了一些实验之后，我说服自己简单地计算所有 2^n 的总和并存储它们是最好的方法。然而，实现一个小集合的效率对于避免这些 O(2^n*n) 的总和的计算花费太长时间至关重要。
我使用整数 0 到 2^n-1 来表示所有子集的集合（幂集）。
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 的最大组数相等到 963，总和为 994。
这张地图的进一步处理取决于 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]
于 2014-07-22T09:07:49.670 回答