77. Combinations

class Solution(object):
    def combine(self, n, k):
        # 思路:dfs
        # 控制一个index,每次往cur里面添加的元素为index->n
        # 下一层的index为index+1
        # 执行完毕后对cur进行pop()
        
        if k > n:
            return []
        self.res = []
        self.k = k
        self.n = n
        cur = []
        self.dfs(cur, 1)
        return self.res

    def dfs(self, cur, idx):
        if len(cur) == self.k:
            self.res.append(cur[:])
        for i in range(idx, self.n + 1):
            cur.append(i)
            self.dfs(cur, i + 1)
            cur.pop()