回溯算法理论：

---

 Leetcode 77. 组合

这道题其实有点绕的我头晕，对于start index的解释我能够理解，但是我很难去想清楚他是如何在一次次递归中变化的因为他在for循环外面扮演我们每一次在一个数字找完了他开头的所有组合之后，就把startindex换到下一个数字去，这样我们就不会找到重复的，但是在for循环里面，他也再遍历

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:

        path = []
        res = []

        def backtracking(n, k, start_index):
            # base case, for collecting res
            if len(path) == k:
                res.append(path[:])
                return 
            
            # recursive case
            # when we are a current point in the path, we start 
            # from here and check possible solutions
            for i in range(start_index, n + 1):
                # add the start index to path
                path.append(i)

                # call the recursive function to rest numbers
                start_index += 1
                backtracking(n, k, start_index)
                
                # make sure to pop the last num added so we can update path
                path.pop()

        backtracking(n, k, 1) 
        return res

剪枝操作后：

这道题的剪枝操作其实思路上也不难理解

就是说当我们在进行递归的时候，如果剩余的数字数量已经不够让我们满足path所需要的长度的时候，就没有必要再继续从那个start index往下分支去找path了，比如上图的情况中我们需要k=4的时候，在一开始start index是1的时候，我们能找到1,2,3,4 但是当我们的start index是2并且path回到只有一个元素的时候，我们最多只能取到2,3,4 反正也凑不够k