回溯篇 – 组合

回溯分为组合篇、排列篇、分割篇和子集篇。 回溯具有高度模板化，以下为模版代码： 组合问题分为以下3种：

• 1 数组中可选择的元素可以至多可以选择一次
  • 1 模版题；
  • 2 循环中的下一个迭代的起始索引+1
• 2 数组中可选择的元素可以重复无限制选取
  • 1 在模版题的基础上；
  • 2 函数入口多增加越界判断（否则会无限循环）；
  • 3 循环中的下一个迭代的起始索引不变。
• 3 数组中可选择的元素可以至多先选择一次，同时返回结果没有重复子数组。
  • 1 在模版题目的基础上
  • 2 先对数组进行排序，使数组中重复元素挨着
  • 3 增加used数组进行去重，nums[i-1] = num[i]则说明重复（该重复为同层之间的重复，同一个树枝中允许重复）

  • // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
    // used[i - 1] == false，说明同一树层candidates[i - 1]使用过

1 组合问题

题目类型一。 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 剪枝版本：

• k – path.size(): 还需要加入的节点数量
• n – (k – path.size()) + 1 : 下标需要在索引左边才能加入足够多的节点数量

2 组合总和

题目类型一。 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

1 模版题； 2 循环中的下一个迭代的起始索引+1

优化版本：

• 1 candidates数组需要排序
• 2 for循环中total+candidates <= target

3 组合总和III

题目类型二。 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。 题目类型二。

1 在模版题的基础上； 2 函数入口多增加越界判断（否则会无限循环）； 3 循环中的下一个迭代的起始索引不变。

优化版本：

• 1 数组需要排序（已经有序）
• 2 for循环中total+candidates <= target

4 组合总和II

题目类型三。 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意：解集不能包含重复的组合。

• 1 在模版题目的基础上
• 2 先对数组进行排序，使数组中重复元素挨着
• 3 增加used数组进行去重，nums[i-1] = num[i]则说明重复（该重复为同层之间的重复，同一个树枝中允许重复）

• // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  // used[i - 1] == false，说明同一树层candidates[i - 1]使用过

直接给出优化版本。

5 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例 1：

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

解题思路：

• 1 递归入口控制组合的长度；
• 2 for循环处控制每次组合可选择的数组范围；

class Solution {
public:
    vector<string> result;
    vector<string> vocabs = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    void traversal(string digits, string path){
        // 控制组合长度
        if (path.size() == digits.size()){
            result.push_back(path);
            return ;
        }
        int digit = digits[path.size()] - '2';
        string letters = vocabs[digit];
        // 控制选择来源
        for(int i=0; i<letters.size(); i++){
            traversal(digits, path+letters[i]);
        }
    }
    
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return {};
        traversal(digits, "");
        return result;
    }
};