溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

LeetCode中如何實現(xiàn)組合總和

發(fā)布時間：2021-12-15 09:22:09 來源：億速云 閱讀：100 作者：小新 欄目：大數(shù)據(jù)

這篇文章主要介紹LeetCode中如何實現(xiàn)組合總和，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！


 

題目描述

找出所有相加之和為 n 的 k 個數(shù)的組合。組合中只允許含有 1 - 9 的正整數(shù)，并且每種組合中不存在重復(fù)的數(shù)字。

說明：

  • 所有數(shù)字都是正整數(shù)。

  • 解集不能包含重復(fù)的組合。

示例 1:

輸入: k = 3, n = 7輸出: [[1,2,4]]
 

示例 2:

輸入: k = 3, n = 9輸出: [[1,2,6], [1,3,5], [2,3,4]]
 

 
 
 
 
---------------------機智的思考線---------------------  
 
 
 
 
---------------------機智的思考線---------------------  
 
 
 
 
---------------------機智的思考線---------------------  
 
 
 
 
   

解題方案

 

思路

  • 標(biāo)簽：遞歸回溯

  • 遞歸終止條件：數(shù)組中包含k個數(shù)，如果和為n則加入結(jié)果集，否則直接返回終止遞歸

  • 遞歸過程：循環(huán)遍歷1-9，將新數(shù)字加入臨時數(shù)組中進入下一層遞歸，出來后再將其移除

  • 回溯的關(guān)鍵在于，添加和移除，保證所有可能性都遍歷到，整體結(jié)構(gòu)和棧類似

LeetCode中如何實現(xiàn)組合總和  
回溯過程
 

代碼

class Solution {    private List<List<Integer>> ans = new ArrayList<>();        public List<List<Integer>> combinationSum3(int k, int n) {        traceBack(k, n, 0, 1, new LinkedList<>());        return ans;    }        public void traceBack(int k, int n, int sum, int begin, LinkedList<Integer> list) {        if(k == 0) {            if(n == sum)                ans.add(new ArrayList<>(list));            return;        }        for(int i = begin; i < 10; i++) {            list.add(i);            traceBack(k - 1, n, sum + i ,i + 1, list);            list.removeLast();        }    }}
 

以上是“LeetCode中如何實現(xiàn)組合總和”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道！

向AI問一下細節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手