[[424324]]

組合總和III

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

找出所有相加之和為 n 的 k 個(gè)數(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]]

思路

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

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

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

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

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

選取過程如圖：

組合總和III

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

回溯三部曲

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

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

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

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

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

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

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

所以代碼如下：

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

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

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

• 確定終止條件

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

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

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

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

所以 ，終止代碼如下：

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

• 單層搜索過程

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

如圖：

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

代碼如下：

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

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

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

class Solution { 
private: 
    vector<vector<int>> result; // 存放結(jié)果集 
    vector<int> path; // 符合條件的結(jié)果 
    // targetSum：目標(biāo)和，也就是題目中的n。 
    // k：題目中要求k個(gè)數(shù)的集合。 
    // sum：已經(jīng)收集的元素的總和，也就是path里元素的總和。 
    // startIndex：下一層for循環(huán)搜索的起始位置。 
    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調(diào)整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; 
    } 
}; 

剪枝

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

如圖：

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

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

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

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

最后C++代碼如下：

class Solution { 
private: 
    vector<vector<int>> result; // 存放結(jié)果集 
    vector<int> path; // 符合條件的結(jié)果 
    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調(diào)整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; 
    } 
}; 

總結(jié)

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

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

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