216. 組合總和 III

找出所有相加之和為 n 的 k 個數(shù)的組合，且滿足下列條件：

只使用數(shù)字1到9
每個數(shù)字 最多使用一次
返回 所有可能的有效組合的列表 奶赔。該列表不能包含相同的組合兩次，組合可以以任何順序返回输虱。

示例 1:
輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒有其他符合的組合了。

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backTracking(int sum, int startIndex, int k, int target) {
        //cout << sum << " " << path.size() << " " <<k <<endl;
        if (path.size() == k && target == sum) {
            result.emplace_back(path);
            return;
        }

        if (path.size() >= k && target != sum) {
            return;
        }

        if (sum > target && path.size() <= k) {
            return;
        }

        for (int i = startIndex; i<= 9 - (k-path.size()) + 1; i++) {
            path.emplace_back(i);
            sum = sum + i;
            //cout << sum << endl;
            backTracking(sum, i+1, k, target);
            sum = sum -i ;
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        path.clear();
        result.clear();
        backTracking(0, 1, k, n);
        return result;
    }
};

知識點：

套用回溯法套路即可脂凶。主要要把圖畫出來宪睹。
for循環(huán)要干什么，每次進(jìn)入迭代要干什么蚕钦、

void backtracking(參數(shù)) {
    if (終止條件) {
        存放結(jié)果;
        return;
    }
    for (選擇：本層集合中元素（樹中節(jié)點孩子的數(shù)量就是集合的大泻岜ぁ）) {
        處理節(jié)點;
        backtracking(路徑，選擇列表); // 遞歸
        回溯冠桃，撤銷處理結(jié)果
    }
}

17. 電話號碼的字母組合

給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合道宅。答案可以按 任意順序 返回食听。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母污茵。

200px-telephone-keypad2svg.png

示例 1：

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

class Solution {
private:
    string path;
    vector<string> result;
    const string letterMap[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    void backTracking(string digits, int index) {
        if (index == digits.size()) {
            result.push_back(path);
            return;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        # for循環(huán)遍歷的是每一層的數(shù)據(jù)
        for (int i = 0 ; i< letters.size(); i++) {
            path.push_back(letters[i]);
            #迭代是進(jìn)入下一層的數(shù)據(jù)
            backTracking(digits, index+1);
            path.pop_back();
        } 
    }
public:
    vector<string> letterCombinations(string digits) {
        path.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backTracking(digits, 0);
        return result;
    }
};

知識點