日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢(xún)
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷(xiāo)解決方案
一篇解讀組合總和III

組合總和III

力扣題目鏈接：https://leetcode-cn.com/problems/combination-sum-iii/

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

說(shuō)明：

  • 所有數(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]]

思路

本題就是在[1,2,3,4,5,6,7,8,9]這個(gè)集合中找到和為n的k個(gè)數(shù)的組合。

相對(duì)于77. 組合，無(wú)非就是多了一個(gè)限制，本題是要找到和為n的k個(gè)數(shù)的組合，而整個(gè)集合已經(jīng)是固定的了[1,...,9]。

想到這一點(diǎn)了，做過(guò)77. 組合之后，本題是簡(jiǎn)單一些了。

本題k相當(dāng)于了樹(shù)的深度，9(因?yàn)檎麄€(gè)集合就是9個(gè)數(shù))就是樹(shù)的寬度。

例如 k = 2，n = 4的話，就是在集合[1,2,3,4,5,6,7,8,9]中求 k(個(gè)數(shù)) = 2, n(和) = 4的組合。

選取過(guò)程如圖：

組合總和III

圖中，可以看出，只有最后取到集合(1，3)和為4 符合條件。

回溯三部曲

確定遞歸函數(shù)參數(shù)

和77. 組合一樣，依然需要一維數(shù)組path來(lái)存放符合條件的結(jié)果，二維數(shù)組result來(lái)存放結(jié)果集。

這里我依然定義path 和 result為全局變量。

至于為什么取名為path?從上面樹(shù)形結(jié)構(gòu)中，可以看出，結(jié)果其實(shí)就是一條根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。

 
 
 
 
    
  
  
  
  
  1. vector> result; // 存放結(jié)果集 
    2. 
  
  
  
  
  2. vector path; // 符合條件的結(jié)果 
    3.

接下來(lái)還需要如下參數(shù)：

  • targetSum(int)目標(biāo)和，也就是題目中的n。
  • k(int)就是題目中要求k個(gè)數(shù)的集合。
  • sum(int)為已經(jīng)收集的元素的總和，也就是path里元素的總和。
  • startIndex(int)為下一層for循環(huán)搜索的起始位置。

所以代碼如下：

 
 
 
 
    
  
  
  
  
  1. vector> result; 
    2. 
  
  
  
  
  2. vector path; 
    3. 
  
  
  
  
  3. void backtracking(int targetSum, int k, int sum, int startIndex) 
    4.

其實(shí)這里sum這個(gè)參數(shù)也可以省略，每次targetSum減去選取的元素?cái)?shù)值，然后判斷如果targetSum為0了，說(shuō)明收集到符合條件的結(jié)果了，我這里為了直觀便于理解，還是加一個(gè)sum參數(shù)。

還要強(qiáng)調(diào)一下，回溯法中遞歸函數(shù)參數(shù)很難一次性確定下來(lái)，一般先寫(xiě)邏輯，需要啥參數(shù)了，填什么參數(shù)。

  • 確定終止條件

什么時(shí)候終止呢?

在上面已經(jīng)說(shuō)了，k其實(shí)就已經(jīng)限制樹(shù)的深度，因?yàn)榫腿個(gè)元素，樹(shù)再往下深了沒(méi)有意義。

所以如果path.size() 和 k相等了，就終止。

如果此時(shí)path里收集到的元素和(sum) 和targetSum(就是題目描述的n)相同了，就用result收集當(dāng)前的結(jié)果。

所以 ，終止代碼如下：

 
 
 
 
    
  
  
  
  
  1. if (path.size() == k) { 
    2. 
  
  
  
  
  2.     if (sum == targetSum) result.push_back(path); 
    3. 
  
  
  
  
  3.     return; // 如果path.size() == k 但sum != targetSum 直接返回 
    4. 
  
  
  
  
  4. } 
    5.
  • 單層搜索過(guò)程

本題和77. 組合區(qū)別之一就是集合固定的就是9個(gè)數(shù)[1,...,9]，所以for循環(huán)固定i<=9

如圖：

處理過(guò)程就是 path收集每次選取的元素，相當(dāng)于樹(shù)型結(jié)構(gòu)里的邊，sum來(lái)統(tǒng)計(jì)path里元素的總和。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. for (int i = startIndex; i <= 9; i++) { 
    2. 
  
  
  
  
  2.     sum += i; 
    3. 
  
  
  
  
  3.     path.push_back(i); 
    4. 
  
  
  
  
  4.     backtracking(targetSum, k, sum, i + 1); // 注意i+1調(diào)整startIndex 
    5. 
  
  
  
  
  5.     sum -= i; // 回溯 
    6. 
  
  
  
  
  6.     path.pop_back(); // 回溯 
    7. 
  
  
  
  
  7. } 
    8.

別忘了處理過(guò)程 和 回溯過(guò)程是一一對(duì)應(yīng)的，處理有加，回溯就要有減!

參照關(guān)于回溯算法，你該了解這些!中的模板，不難寫(xiě)出如下C++代碼：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. private: 
    3. 
  
  
  
  
  3.     vector> result; // 存放結(jié)果集 
    4. 
  
  
  
  
  4.     vector path; // 符合條件的結(jié)果 
    5. 
  
  
  
  
  5.     // targetSum：目標(biāo)和，也就是題目中的n。 
    6. 
  
  
  
  
  6.     // k：題目中要求k個(gè)數(shù)的集合。 
    7. 
  
  
  
  
  7.     // sum：已經(jīng)收集的元素的總和，也就是path里元素的總和。 
    8. 
  
  
  
  
  8.     // startIndex：下一層for循環(huán)搜索的起始位置。 
    9. 
  
  
  
  
  9.     void backtracking(int targetSum, int k, int sum, int startIndex) { 
    10. 
  
  
  
  
  10.         if (path.size() == k) { 
    11. 
  
  
  
  
  11.             if (sum == targetSum) result.push_back(path); 
    12. 
  
  
  
  
  12.             return; // 如果path.size() == k 但sum != targetSum 直接返回 
    13. 
  
  
  
  
  13.         } 
    14. 
  
  
  
  
  14.         for (int i = startIndex; i <= 9; i++) { 
    15. 
  
  
  
  
  15.             sum += i; // 處理 
    16. 
  
  
  
  
  16.             path.push_back(i); // 處理 
    17. 
  
  
  
  
  17.             backtracking(targetSum, k, sum, i + 1); // 注意i+1調(diào)整startIndex 
    18. 
  
  
  
  
  18.             sum -= i; // 回溯 
    19. 
  
  
  
  
  19.             path.pop_back(); // 回溯 
    20. 
  
  
  
  
  20.         } 
    21. 
  
  
  
  
  21.     } 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23. public: 
    24. 
  
  
  
  
  24.     vector> combinationSum3(int k, int n) { 
    25. 
  
  
  
  
  25.         result.clear(); // 可以不加 
    26. 
  
  
  
  
  26.         path.clear();   // 可以不加 
    27. 
  
  
  
  
  27.         backtracking(n, k, 0, 1); 
    28. 
  
  
  
  
  28.         return result; 
    29. 
  
  
  
  
  29.     } 
    30. 
  
  
  
  
  30. }; 
    31.

剪枝

這道題目，剪枝操作其實(shí)是很容易想到了，想必大家看上面的樹(shù)形圖的時(shí)候已經(jīng)想到了。

如圖：

已選元素總和如果已經(jīng)大于n(圖中數(shù)值為4)了，那么往后遍歷就沒(méi)有意義了，直接剪掉。

那么剪枝的地方一定是在遞歸終止的地方剪，剪枝代碼如下：

 
 
 
 
    
  
  
  
  
  1. if (sum > targetSum) { // 剪枝操作 
    2. 
  
  
  
  
  2.     return; 
    3. 
  
  
  
  
  3. } 
    4.

和77.組合 一樣，for循環(huán)的范圍也可以剪枝，i <= 9 - (k - path.size()) + 1就可以了。

最后C++代碼如下：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. private: 
    3. 
  
  
  
  
  3.     vector> result; // 存放結(jié)果集 
    4. 
  
  
  
  
  4.     vector path; // 符合條件的結(jié)果 
    5. 
  
  
  
  
  5.     void backtracking(int targetSum, int k, int sum, int startIndex) { 
    6. 
  
  
  
  
  6.         if (sum > targetSum) { // 剪枝操作 
    7. 
  
  
  
  
  7.             return; // 如果path.size() == k 但sum != targetSum 直接返回 
    8. 
  
  
  
  
  8.         } 
    9. 
  
  
  
  
  9.         if (path.size() == k) { 
    10. 
  
  
  
  
  10.             if (sum == targetSum) result.push_back(path); 
    11. 
  
  
  
  
  11.             return; 
    12. 
  
  
  
  
  12.         } 
    13. 
  
  
  
  
  13.         for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝 
    14. 
  
  
  
  
  14.             sum += i; // 處理 
    15. 
  
  
  
  
  15.             path.push_back(i); // 處理 
    16. 
  
  
  
  
  16.             backtracking(targetSum, k, sum, i + 1); // 注意i+1調(diào)整startIndex 
    17. 
  
  
  
  
  17.             sum -= i; // 回溯 
    18. 
  
  
  
  
  18.             path.pop_back(); // 回溯 
    19. 
  
  
  
  
  19.         } 
    20. 
  
  
  
  
  20.     } 
    21. 
  
  
  
  
  21.  
    22. 
  
  
  
  
  22. public: 
    23. 
  
  
  
  
  23.     vector> combinationSum3(int k, int n) { 
    24. 
  
  
  
  
  24.         result.clear(); // 可以不加 
    25. 
  
  
  
  
  25.         path.clear();   // 可以不加 
    26. 
  
  
  
  
  26.         backtracking(n, k, 0, 1); 
    27. 
  
  
  
  
  27.         return result; 
    28. 
  
  
  
  
  28.     } 
    29. 
  
  
  
  
  29. }; 
    30.

總結(jié)

開(kāi)篇就介紹了本題與77.組合的區(qū)別，相對(duì)來(lái)說(shuō)加了元素總和的限制，如果做完77.組合再做本題在合適不過(guò)。

分析完區(qū)別，依然把問(wèn)題抽象為樹(shù)形結(jié)構(gòu)，按照回溯三部曲進(jìn)行講解，最后給出剪枝的優(yōu)化。 

相信做完本題，大家對(duì)組合問(wèn)題應(yīng)該有初步了解了。


文章名稱(chēng)：一篇解讀組合總和III
URL標(biāo)題：http://www.5511xx.com/article/dpsdiso.html