華為面試題，求答案？

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

動態(tài)規(guī)劃 + hash濾重，復雜度2^N， 目前沒更好的算法

windoze

回復 2# koolcoy

復雜度O(2^N)沒跑啊，結果的個數就是2^N-N-1個，復雜度沒法更低了。

Dannysd

智商太低，沒看懂。。。。捂臉淚奔

udb6688

就是8個數值當中，隨便取幾個來加起來。求代碼

sig13

全部的組合打出來倒很容易，可是萬一有兩個輸入一樣怎么辦呢？簡單算法好像照不住。

bruceteen

每個數字只有兩個狀態(tài)，分別是『選中』和『不選中』，因此只有 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差不多就這個意思