如何將數組的每個元素與同一數組的其他元素一起添加？

Question

假設我有一個數組

a[3]={1,3,8} 

我想要的輸出是含有通過添加從陣列的數字，以及數組a的元素獲得的號碼的數組。即

b[0]=1 
b[1]=3 
b[2]=8 
b[3]=4 //(1+3) 
b[4]=9 //(1+8) 
b[5]=11 //(3+8) 
b[6]=12 //(1+3+8) 

我該怎麼做？

Answer 1

所以你想要生成一組數字的所有可能的子集並列出它們的總和。

首先，你想枚舉所有的子集。由於有2^N亞羣含有N元素的一組，就可以簡單地通過從0自然數迭代到1 << (sizeof(arr)/sizeof(arr[0]))和治療數的二進制表示以下面的方式執行以下操作：如果一個特定的位被設置在k位置，那麼k th元素在當前生成的子集中，否則它不是。

然後，您應該將所有選定的元素添加在一起，並將結果存儲在另一個陣列的下一個插槽中（顯然，大小爲2^N）。

#define COUNT(a) (sizeof(a)/sizeof(a[0])) 
#include <limits.h> // for CHAR_BIT 

unsigned a[3] = { 1, 3, 8 }; 
unsigned sums[1 << COUNT(a)] = { 0 }; 

for (unsigned i = 0; i < COUNT(sums); i++) { 
    for (unsigned j = 0; j < sizeof(i) * CHAR_BIT; j++) { 
     if ((i >> j) & 1) { 
      sums[i] += a[j]; 
     } 
    } 
} 

for (unsigned i = 0; i < COUNT(sums); i++) { 
    printf("%d\n", sums[i]); 
} 

Answer 2

我會做這樣的：

b[0] = 0; //This is not listed in the question, but should be included in the result IMHO. 
for(long i = 0; i < elementsA; i++) { 
    long preexistingElements = 1 << i; 
    long curElement = a[i]; 
    for(long j = 0; j < preexistingElements; j++) { 
     b[j + preexistingElements] = b[j] + curElement; 
    } 
} 

該算法是在結果陣列的大小線性作爲它的每個元素被計算以恆定成本。

如果你真的必須排除零和希望的malloc結果數組，轉身算法所以將b從零元素後作爲最後一個元素填補。