77. 组合

对着 在 回溯算法理论基础 给出的 代码模板，来做本题组合问题，大家就会发现 写回溯算法套路。

在回溯算法解决实际问题的过程中，大家会有各种疑问，先看视频介绍，基本可以解决大家的疑惑。

本题关于剪枝操作是大家要理解的重点，因为后面很多回溯算法解决的题目，都是这个剪枝套路。

题目链接/文章讲解：https://programmercarl.com/0077.组合.html
视频讲解：https://www.bilibili.com/video/BV1ti4y1L7cv
剪枝操作：https://www.bilibili.com/video/BV1wi4y157er

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

思考

回溯的模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。

图中可以发现n相当于树的宽度，k相当于树的深度。

1. 组合问题需要start_index来避免重复结果。
2. 可以剪枝

class Solution:
    def __init__(self):
        self.res_list = []
        self.res_list_all = []
    def backtracking(self,n,k,start_index):
        if k == len(self.res_list):
            self.res_list_all.append(self.res_list[:])
            return
        else:
            for i in range(start_index,n+1):
                if len(self.res_list)+ 1 + n - i < k:
                     break
                self.res_list.append(i)
                #print(self.res_list)
                self.backtracking(n,k,i+1)
                self.res_list.pop()
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.backtracking(n,k,1)
        return self.res_list_all

216.组合总和III

如果把 组合问题理解了，本题就容易一些了。

题目链接/文章讲解：https://programmercarl.com/0216.组合总和III.html
视频讲解：https://www.bilibili.com/video/BV1wg411873x
找出所有相加之和为 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. 总和大于target时，提前返回。
2. 元素个数>k时,break

class Solution:
    def __init__(self):
        self.path = []
        self.res_list_all = []
        self.sum = 0
    def backtracking(self,candidates,target,k,start_index):
        # 剪枝1
        if self.sum > target:
            return 
        if len(self.path) == k:
            if self.sum == target:
                self.res_list_all.append(self.path[:])
            return 
        else:
            for i in range(start_index,len(candidates)):
                # 剪枝2
                if len(self.path)>=k:
                    break
                self.path.append(candidates[i])
                self.sum+=candidates[i] 
                self.backtracking(candidates,target,k,i+1)
                self.path.pop()
                self.sum-=candidates[i]
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        candidates = [1,2,3,4,5,6,7,8,9]
        self.backtracking(candidates,n,k,0)
        return self.res_list_all

17.电话号码的字母组合

本题大家刚开始做会有点难度，先自己思考20min，没思路就直接看题解。

题目链接/文章讲解：https://programmercarl.com/0017.电话号码的字母组合.html
视频讲解：https://www.bilibili.com/video/BV1yV4y1V7Ug
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

class Solution:
    def __init__(self):
        self.letterMap = [
            "",     # 0
            "",     # 1
            "abc",  # 2
            "def",  # 3
            "ghi",  # 4
            "jkl",  # 5
            "mno",  # 6
            "pqrs", # 7
            "tuv",  # 8
            "wxyz"  # 9
        ]
        self.result = []
        self.s = []
    def backtracking(self,digits,index):
        if len(digits) == len(self.s):
            self.result.append(''.join(self.s))
            return
        for c in self.letterMap[int(digits[index])]:
            self.s.append(c)
            self.backtracking(digits,index+1)
            self.s.pop()
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return self.result
        self.backtracking(digits,0)
        return self.result