只能说越到后面越难坚持，加油

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

未剪枝

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        self.backtracking(n,k,1,[],result)
        return result

    def backtracking(self,n,k,index,path,result):
        if len(path) == k:
            result.append(path[:]) # 注意path的拷贝方式
            return
        for i in range(index,n+1):
            path.append(i)
            self.backtracking(n,k,i+1,path,result) #这里改成index+1会返回所有组合（包括重复的）
            path.pop()

剪枝

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        self.backtracking(n,k,1,[],result)
        return result

    def backtracking(self,n,k,index,path,result):
        if len(path) == k:
            result.append(path[:]) # 注意path的拷贝方式
            return
        for i in range(index,n-(k-len(path))+2): # 这里的n-(k-len(path))+2是为了剪枝，因为如果n-(k-len(path))+2还小于k，那么就没有必要继续遍历了
            path.append(i)
            self.backtracking(n,k,i+1,path,result) #这里改成index+1会返回所有组合（包括重复的）
            path.pop()

解释一下这个剪枝的地方：
need = k - len(path)，i一直到n，共有n-i+1个元素，剩余元素至少要大于等于need才行，因此n-i+1 >= need，即n-i+1 >= k - len(path)，即n-(k-len(path))+1 <= n，但是python的range是左闭右开的，右边取不到，所以要+1变成n-(k-len(path))+2

组合总和III

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字最多使用一次

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        self.backtracking(n,k,0,1,[],result)
        return result
    def backtracking(self,targetsum,k,cursum,index,path,result):
        if cursum > targetsum:
            return 
        if len(path) == k :
            if targetsum == cursum:
                result.append(path[:])
            return 
        for i in range(index,9-(k-len(path))+2):
            cursum += i
            path.append(i)
            self.backtracking(targetsum,k,cursum,i+1,path,result)
            cursum -= i
            path.pop()

这道题比上一道题多的剪枝的内容是当前和大于目标和时，直接返回
以及在回溯的时候别忘了更新当前和

电话号码的字母组合

17. 电话号码的字母组合

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

class Solution:
    def __init__(self):
        self.lettermap=[
            '',
            '',
            'abc',
            'def',
            'ghi',
            'jkl',
            'mno',
            'pqrs',
            'tuv',
            'wxyz'
        ]
        self.result = []
        self.s = ''
    def backtracking(self,digits,index):
        if index == len(digits): #终止条件深度等于位数
            self.result.append(self.s)
            return 
        digit = int(digits[index]) #字符形式转化，便于查字典
        letter = self.lettermap[digit] #对应层的字符串
        for i in letter: #实现分叉
            self.s += i
            self.backtracking(digits,index + 1) #深度探索
            self.s = self.s[:-1] #回溯，删掉最后一个
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return self.result
        self.backtracking(digits,0)
        return self.result