华为面试题，求答案？

udb6688

从键盘输入8个数字如：1，2，3，4，5，6，7，8；
根据这8个数字完成任意几个的组合和;
如：
1+2,1+3,1+4,1+5,1+6,1+7,1+8;
1+2+3,1+2+4,1+2+5,.....;
1+2+3+4,1+2+3+5,...
1+2+3+4+5,1+2+3+4+6,....
2+3,2+4....
2+3+4,2+3+5..



有谁能解?

koolcoy

动态规划 + hash滤重，复杂度2^N， 目前没更好的算法

windoze

回复 2# koolcoy

复杂度O(2^N)没跑啊，结果的个数就是2^N-N-1个，复杂度没法更低了。

Dannysd

智商太低，没看懂。。。。捂脸泪奔

udb6688

就是8个数值当中，随便取几个来加起来。求代码

sig13

全部的组合打出来倒很容易，可是万一有两个输入一样怎么办呢？简单算法好像照不住。

bruceteen

每个数字只有两个状态，分别是『选中』和『不选中』，因此只有 2^8 个组合
假如 共选择0个 和 共选择1个 的情况，那也只有 2^8 -1 - 8 个组合

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.     const unsigned N = 8;
   
6. 
   
7.     for( unsigned i=1; i!=(1u<<N); ++i ) // i不从0开始，是为了剔除『一个都没选择』的情况
   
8.     {
   
9.         if( (i&(i-1)) == 0 ) // 剔除『只选择了一个』的情况
   
10.             continue;
    
11. 
    
12.         // 输出
    
13.         for( unsigned j=0; j!=N; ++j )
    
14.             if( i&(1u<<j) )
    
15.                 printf( "%d+", j+1 );
    
16.         printf( "\n" );
    
17.     }
    
18. 
    
19.     return 0;
    
20. }

复制代码

udb6688

回复 8# bruceteen


   太牛了，暂时不能理解，能不能代码写全，如果从键盘输入，43，72，12，32，19，9，2，14这8个数字，求打印出所有结果

koolcoy

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int main() {
   
5.         int input[8] = {1,2,3,4,5,6,7,8};
   
6.         int sum[256];
   
7. 
   
8.         sum[0] = 0;
   
9.         sum[1] = input[0];
   
10. 
    
11.         int idx = 2;
    
12.         for (int i = 1; i < 8; ++i, idx *= 2) {
    
13.                 for (int j = 0; j < idx; ++j) {
    
14.                         sum[idx + j] = input[i] + sum[j];
    
15.                 }
    
16.         }
    
17.         for (int i = 0; i < 256; ++i) {
    
18.                 printf("%d ", sum[i]);
    
19.         }
    
20.         return 0;
    
21. }
    

复制代码

DP差不多就这个意思