給定數量的組合加起來爲X

Question

儘管它不應該很難，但我一直在堅持。我需要在C中創建一個函數，計算並顯示給定數字的所有可能組合（不重複），其中每個組合的數字（僅範圍從1到9）在添加時給出指定的總和。

我想這不是最清楚的解釋，所以這裏有一個例子：計算5個號碼（從1到9），加起來28

的所有集合我會很感激，如果有人可以解釋這個。

Answer 1

由於只有512種不同的選擇，您可以輕鬆地預先計算結果。

預先計算：

• 準備一個空的映射（總和=>設置（設定（位））），命名lookup。 （1..9）
  • 計算它的sum。
  • 如果lookup沒有密鑰sum，請創建一個新條目，一個空集。
  • 添加subset到lookup[sum]

查找一個sum：

• 如果lookup有鑰匙sum，回報（副本）的條目。否則返回一個空集。

---

爲了解決一些C的低級別的煩躁的：

一種地圖INT => x僅僅是一個數組。一組x也只是一個數組+長度。

既然你已經知道了最大的鍵映射的陣列可以被分配爲靜態的，45

您可以預先估計最大的一套套爲好，或使用動態分配的（更有效）。如果您不關心空間，您可以輕鬆過度分配（最多512個條目）。我認爲你不想過度分配這麼多，所以你還可以學習如何動態分配。

一組數字可以表示爲一個9位的位掩碼（內存中的16位）。然後他們很容易枚舉。

的實際類型爲lookup草圖：

typedef setOfDigits int16; 

struct setOfSets{ 
    setOfDigits* data; 
    int16 count; //the actual amount of sets in the set 
    int16 space; //the size of the allocated array 
} 

setOfSets lookup[46]; 

實際類型lookup的草圖，沒有動態分配或struct S：

int16 lookup[46][512]; 
int16 lookupLength[46]; 

請注意，如果您等同space:=count，那麼你永遠不會過度分配，但你經常重新分配，這是更容易實現，但可能效率低下（但代碼的運行一次，所以嘿）

當然，高級語言（甚至C++）具有本地（javascript）或通過標準庫（C++，Java）的動態數組。在C中，你必須依靠realloc。