day22| 回溯算法

三道题目 组合 组合之和 和电话号码

组合之和和组合异曲同工。大概逻辑就是

• 首先明确组合和排序的区别。 在组合里面我们要确保不能有重复的序列
• 我们保持整体序列是有序的，这样就避免了在遍历的过程中出现重复的状况
• 假设我们输入一个 cur 那么我们就遍历所有比 cur 大的数
• 在代码中就相当于while last<=n:这里的遍历

def dfs(path):
    if len(path)==k:
        res.append(path[:])
        return
    last = path[-1] if path else 0
    # 剪枝
    if len(path)+n-last<k:
        return
    last+=1
    while last<=n:
        dfs(path+[last])
        last+=1