class Solution:
    res = []
    def combine(self, n: int, k: int) -> List[List[int]]:
        cnt = 0
        idx = 1
        self.res = []
        tmp = []
        self.dfs(cnt, n, k, idx, tmp)
        return self.res

    def dfs(self, cnt, n, k, idx, tmp):
		# 这里需要注意，是n+1, 否则最后一个结果拿不到。
		# 一定要结合代码输出快速的定位问题
        if idx > n+1: 
            return    
        if cnt == k:
            print(tmp)
            self.res.append(tmp[:])
        elif cnt < k:
            tmp.append(idx)
            self.dfs(cnt+1, n, k, idx+1, tmp)
            del tmp[-1]
            self.dfs(cnt, n, k, idx+1, tmp)