組合總和 II

40。組合總和 II

難度：中

主題：數組，回溯

給定一組候選數字（candidates）和一個目標數字（target），找出候選數字總和達到目標的所有唯一組合。

候選中的每個數字在組合中只能使用一次。

注意：解決方案集不得包含重複的組合。

範例1：

• 輸入： 候選人 = [10,1,2,7,6,1,5]，目標 = 8
• 輸出： [[1,1,6], [1,2,5], [1,7], [2,6]]

範例2：

• 輸入： 候選人 = [2,5,2,1,2]，目標 = 5
• 輸出： [[1,2,2], [5]]

約束：

• 1
• 1
• 1

解：

我們可以使用回溯法。關鍵思想是先對陣列進行排序以輕鬆處理重複項，然後使用回溯探索所有可能的組合。

讓我們用 PHP 實作這個解決方案：40。組合和 II

解釋：

1. 排序：對候選數組進行排序，以便輕鬆處理重複項並確保組合按排序順序形成。
2. 回溯：回溯函數用來探索所有可能的組合。
   • 如果目標變為零，我們將目前組合加入結果。
   • 我們從目前索引開始迭代候選人。如果候選與前一個相同，我們會跳過它以避免重複組合。
   • 我們從目標中減去目前候選，並使用新目標和下一個索引遞歸呼叫回溯函數。
   • 遞歸呼叫將繼續，直到我們找到有效的組合或窮盡所有可能性。
3. 剪枝：如果候選人超過了目標，我們會提前跳出循環，因為更多候選人也將超過目標。

此程式碼將輸出總和達到目標的所有唯一組合，同時確保每個候選在每個組合中僅使用一次。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是組合總和 II的詳細內容。更多資訊請關注PHP中文網其他相關文章！