[[424324]]

組合總和III

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

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

說明：

• 所有數字都是正整數。
• 解集不能包含重復的組合。

示例 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]這個集合中找到和為n的k個數的組合。

相對于77. 組合，無非就是多了一個限制，本題是要找到和為n的k個數的組合，而整個集合已經是固定的了[1,...,9]。

想到這一點了，做過77. 組合之后，本題是簡單一些了。

本題k相當于了樹的深度，9(因為整個集合就是9個數)就是樹的寬度。

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

選取過程如圖：

組合總和III

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

回溯三部曲

確定遞歸函數參數

和77. 組合一樣，依然需要一維數組path來存放符合條件的結果，二維數組result來存放結果集。

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

至于為什么取名為path?從上面樹形結構中，可以看出，結果其實就是一條根節點到葉子節點的路徑。

vector<vector<int>> result; // 存放結果集 
vector<int> path; // 符合條件的結果 

接下來還需要如下參數：

• targetSum(int)目標和，也就是題目中的n。
• k(int)就是題目中要求k個數的集合。
• sum(int)為已經收集的元素的總和，也就是path里元素的總和。
• startIndex(int)為下一層for循環搜索的起始位置。

所以代碼如下：

vector<vector<int>> result; 
vector<int> path; 
void backtracking(int targetSum, int k, int sum, int startIndex) 

其實這里sum這個參數也可以省略，每次targetSum減去選取的元素數值，然后判斷如果targetSum為0了，說明收集到符合條件的結果了，我這里為了直觀便于理解，還是加一個sum參數。

還要強調一下，回溯法中遞歸函數參數很難一次性確定下來，一般先寫邏輯，需要啥參數了，填什么參數。

• 確定終止條件

什么時候終止呢?

在上面已經說了，k其實就已經限制樹的深度，因為就取k個元素，樹再往下深了沒有意義。

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

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

所以 ，終止代碼如下：

if (path.size() == k) { 
    if (sum == targetSum) result.push_back(path); 
    return; // 如果path.size() == k 但sum != targetSum 直接返回 
} 

• 單層搜索過程

本題和77. 組合區別之一就是集合固定的就是9個數[1,...,9]，所以for循環固定i<=9

如圖：

處理過程就是 path收集每次選取的元素，相當于樹型結構里的邊，sum來統計path里元素的總和。

代碼如下：

for (int i = startIndex; i <= 9; i++) { 
    sum += i; 
    path.push_back(i); 
    backtracking(targetSum, k, sum, i + 1); // 注意i+1調整startIndex 
    sum -= i; // 回溯 
    path.pop_back(); // 回溯 
} 

別忘了處理過程 和 回溯過程是一一對應的，處理有加，回溯就要有減!

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

class Solution { 
private: 
    vector<vector<int>> result; // 存放結果集 
    vector<int> path; // 符合條件的結果 
    // targetSum：目標和，也就是題目中的n。 
    // k：題目中要求k個數的集合。 
    // sum：已經收集的元素的總和，也就是path里元素的總和。 
    // startIndex：下一層for循環搜索的起始位置。 
    void backtracking(int targetSum, int k, int sum, int startIndex) { 
        if (path.size() == k) { 
            if (sum == targetSum) result.push_back(path); 
            return; // 如果path.size() == k 但sum != targetSum 直接返回 
        } 
        for (int i = startIndex; i <= 9; i++) { 
            sum += i; // 處理 
            path.push_back(i); // 處理 
            backtracking(targetSum, k, sum, i + 1); // 注意i+1調整startIndex 
            sum -= i; // 回溯 
            path.pop_back(); // 回溯 
        } 
    } 
 
public: 
    vector<vector<int>> combinationSum3(int k, int n) { 
        result.clear(); // 可以不加 
        path.clear();   // 可以不加 
        backtracking(n, k, 0, 1); 
        return result; 
    } 
}; 

剪枝

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

如圖：

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

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

if (sum > targetSum) { // 剪枝操作 
    return; 
} 

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

最后C++代碼如下：

class Solution { 
private: 
    vector<vector<int>> result; // 存放結果集 
    vector<int> path; // 符合條件的結果 
    void backtracking(int targetSum, int k, int sum, int startIndex) { 
        if (sum > targetSum) { // 剪枝操作 
            return; // 如果path.size() == k 但sum != targetSum 直接返回 
        } 
        if (path.size() == k) { 
            if (sum == targetSum) result.push_back(path); 
            return; 
        } 
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝 
            sum += i; // 處理 
            path.push_back(i); // 處理 
            backtracking(targetSum, k, sum, i + 1); // 注意i+1調整startIndex 
            sum -= i; // 回溯 
            path.pop_back(); // 回溯 
        } 
    } 
 
public: 
    vector<vector<int>> combinationSum3(int k, int n) { 
        result.clear(); // 可以不加 
        path.clear();   // 可以不加 
        backtracking(n, k, 0, 1); 
        return result; 
    } 
}; 

總結

開篇就介紹了本題與77.組合的區別，相對來說加了元素總和的限制，如果做完77.組合再做本題在合適不過。

分析完區別，依然把問題抽象為樹形結構，按照回溯三部曲進行講解，最后給出剪枝的優化。 

相信做完本題，大家對組合問題應該有初步了解了。