如评论中所述,由于数字仅在1到30之间,因此该问题具有快速解决方案。我在C语言中进行了测试,在您给出的示例中,它只需要毫秒级别的时间,并且将很好地扩展。复杂度为O(n + k),其中n是列表A
的长度,k是列表B
的长度,但具有很高的常数因子(有28,598种可能性可以得到1到30的总和)。
#define WIDTH 30000
#define MAXNUMBER 30
int create_combination(unsigned char comb[WIDTH][MAXNUMBER+1],
int n,
unsigned char i,
unsigned char len,
unsigned char min,
unsigned char sum) {
unsigned char j;
if (len == 1) {
if (n+1>=WIDTH) {
printf("not enough space!\n");
exit(-1);
}
comb[n][i] = sum;
for (j=0; j<=i; j++)
comb[n+1][j] = comb[n][j];
n++;
return n;
}
for (j=min; j<=sum/len; j++) {
comb[n][i] = j;
n = create_combination(comb, n, i+1, len-1, j, sum-j);
}
return n;
}
int main(void)
{
unsigned char A[6] = { 7, 4, 9, 1, 15, 2 };
unsigned char B[5] = { 11, 18, 14, 8, 3 };
unsigned char combinations[WIDTH][MAXNUMBER+1];
unsigned char needed[WIDTH][MAXNUMBER];
unsigned char numbers[MAXNUMBER];
unsigned char sums[MAXNUMBER];
unsigned char i, j, k;
int n=0, m;
memset(combinations, 0, sizeof combinations);
memset(needed, 0, sizeof needed);
memset(numbers, 0, sizeof numbers);
memset(sums, 0, sizeof sums);
for (i=2; i<=MAXNUMBER; i++) {
for (j=2; j<=i; j++) {
for (k=1; k<=MAXNUMBER; k++)
combinations[n][k] = 0;
combinations[n][0] = i;
n = create_combination(combinations, n, 1, j, 1, i);
}
}
for (m=0; m<n; m++)
for (i=1; i<=MAXNUMBER && combinations[m][i] != 0; i++)
needed[m][combinations[m][i]-1]++;
for (m=0; m<6; m++)
if (numbers[A[m]-1] < MAXNUMBER)
numbers[A[m]-1]++;
for (m=0; m<5; m++)
sums[B[m]-1] = 1;
for (m=0; m<n; m++) {
if (sums[combinations[m][0]-1] == 0)
continue;
for (i=0; i<MAXNUMBER; i++) {
if (numbers[i] < needed[m][i])
break;
}
if (i<MAXNUMBER)
continue;
for (j=1; j<=MAXNUMBER && combinations[m][j] != 0; j++) {
printf(" %s %d", j>1 ? "+" : "", combinations[m][j]);
}
printf(" = %d\n", combinations[m][0]);
}
return 0;
}
1 + 2 = 3
1 + 7 = 8
2 + 9 = 11
4 + 7 = 11
1 + 4 + 9 = 14
1 + 2 + 4 + 7 = 14
1 + 2 + 15 = 18
2 + 7 + 9 = 18