216.组合总和III

一样是回溯三部曲，区别在于这次每个节点的集合是固定的1~0，剪枝为所求和大于target就return。

  • 确定终止条件 如果path.size() == k相，就终止。如果此时path里收集到的元素和（sum） 和targetSum（就是题目描述的n）相同了，就用result收集当前的结果。
  • 单层搜索过程 path收集每次选取的元素，相当于树型结构里的边，sum来统计path里元素的总和。处理过程和回溯过程是一一对应的，处理有加，回溯就要有减！可以通过每次都计算和免去回溯Sum，但path是要回溯的。
//C++
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum3(int k, int n) {
        BackTracking(n, k, 1, 0);
        return res;
    }
    void BackTracking(int target, int k, int startIndex, int sum) {
        if (path.size() == k) {
            if (sum == target) res.push_back(path);
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i;
            path.push_back(i);
            if (sum > target) {
                sum -= i;
                path.pop_back();
                return;
            }
            BackTracking(target, k, i + 1, sum);
            sum -= i;
            path.pop_back();
        }
    }
};3

//C#
public class Solution {
    IList<IList<int>> res = new List<IList<int>>();
    List<int> path = new List<int>(); 
    public IList<IList<int>> CombinationSum3(int k, int n) {
        BackTracking(n, k , 1, 0);
        return res;
    }
    public void BackTracking(int target, int k, int startIndex, int sum) {
        if (path.Count == k) {
            if (sum == target) res.Add(new List<int>(path));
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i;
            path.Add(i);
            if (sum > target) {
                sum -= i;
                path.RemoveAt(path.Count - 1);
                return;
            }
            BackTracking(target, k, i + 1, sum);
            sum -= i;
            path.RemoveAt(path.Count - 1);
        }
    }
}

17.电话号码的字母组合

不同集合的组合。 注意这里for循环，可不像是在前两题中从startIndex开始遍历的。因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而77. 组合和216.组合总和III 都是求同一个集合中的组合！也就是说树的深度K（startIndex）和每一层集合内的元素无关也不同步了，所以for循环遍历的是节点内的集合也和startIndex无关，startIndex +1遍历完所有数字即可。

class Solution {
public:
    vector<string> res;
    string path;
    const string letterMap[10] = {
    "", // 0
    "", // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz", // 9
    };  
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) {
            return res;
        }
        BackTracking(digits, 0);
        return res;
    }
    void BackTracking(string& digits, int index){
        if (index == digits.size()) {
            res.push_back(path);
            return;
        }
        int digit = digits[index] -'0';
        string letters = letterMap[digit];
        for (int i = 0; i < letters.size(); i++) {
            path.push_back(letters[i]);
            BackTracking(digits, index + 1);
            path.pop_back();
        }
    }
};
  • index是输入的数字遍历到第几个了，也是控制递归的深度，也是暴力的index层for循环。
  • 注意这道题树的每层节点遍历的是字母集合，数从上到下遍历的是输入的数字集合，是不同集合的组合问题，而前两道题从上到下遍历的每层节点，分支依据都是数字集合，为了避免重复要在for循环里面加startIndex，而这道题每一层节点之间没关系不需要去重也，就是固定的字母集合，也就是树的宽度就是字母集合的大小也是for循环的区间。
  • 回溯的for循环本质就是暴力多层for的动态版，想一想暴力for循环怎么写，写回溯for就会更清晰了。
  • 这道题没法剪枝的原因是，不存在节点越用越少的情况，固定是字母集合的大小。
  • 相同集合的组合问题每一层的.
  • 小细节，index == digits.size()，实际index多一位才结束。 alt