在JavaScript中生成所需組合

在給定的問題陳述中，我們必須生成給定輸入的所需組合。並使用Javascript程式設計來編寫解決方案。

理解問題

在這個問題中，我們將得到從1到9的整數。每個組合都應該是數字的唯一集合。該函式應識別大小為m的所有可能的組合，並且這些大小為m的項的總和應為n。

例如，如果m的值為3，n的值為6，則組合應為[1, 2, 3]。因此，輸出陣列中的項1、2和3介於1到9之間，所有這些項的總和為6，因為n的值為6，m的值為3，所以存在3個項。

給定問題的邏輯

該演算法的邏輯是建立一個程式碼來查詢總和為目標值n且長度為m的數字組合。為了獲得這些組合，我們將採用遞迴函式。然後，我們將定義一個函式並使用m和n作為函式的輸入。還有一個搜尋函式，用於透過從給定值開始查詢所有可能的組合。最後，該函式將啟動遞迴過程並返回結果。

演算法

步驟1：將組合的大小定義為m，將目標總和的限制定義為n。

步驟2：建立一個函式，該函式將查詢所有可能的組合的總和，並將引數作為m和n傳遞。

步驟3：將生成的陣列組合儲存在一個新的陣列中，並將其初始化為空。

步驟4：建立一個遞迴函式來搜尋從特定值開始的各種數字組合。

步驟5：當m和n的值都等於零時，此函式將結束。在這種情況下，當前項被推入結果陣列以儲存組合。

步驟6：如果不存在基本情況，則函式將繼續探索組合。如果值超過9，則表示沒有更多數字需要考慮。

步驟7：然後，如果包含當前值，我們將遞迴調用搜索函式，然後將其與字首連線起來。

步驟8：程式碼將使用初始引數調用搜索函式以啟動遞迴過程。並給出所有所需的組合作為結果。

示例

const m = 3, n = 9;
//Function for finding all possible combinations
const findSum = (m, n) => {
   const res = [];

   const search = (from, prefix, m, n) => {
      if (m === 0 && n === 0) {
         res.push(prefix);
         return;
      }
      if (from > 9) return;

      search(from + 1, prefix.concat(from), m - 1, n - from);
      search(from + 1, prefix, m, n);
   };

   search(1, [], m, n);
   return res;
};

console.log(findSum(m, n));

輸出

[ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 2, 3, 4 ] ]

複雜度

由於該函式探索所有可能的組合，因此時間複雜度與有效組合的數量成正比。組合取決於m和n的值。因此，時間複雜度為O(2^n)，其中n是目標總和。程式碼的空間複雜度是透過用於儲存組合結果的空間計算的。因此，在最壞的情況下，當所有可能的組合都有效時，空間複雜度也是O(2^n)。

結論

我們建立的函式有效地使用回溯技術生成了所有可能的數字組合，這些組合的總和等於給定的目標值，並具有指定的長度。但重要的是要考慮時間和空間複雜度的指數增長，這可能會影響大型輸入值下的效能。

更新於：2023年8月14日

263 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始
廣告