from typing import List


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

    def dfs(self,begin, end, k, rlt,combs):
        if end -begin+1<k:
            return

        if k == 0:
            combs.append(rlt.copy())

        for i in range(begin, end+1):
            rlt.append(i)
            self.dfs(i+1, end, k-1, rlt,combs)
            rlt.pop(-1)

        pass

sol=Solution()
rlt =sol.combine(4,2)
print(rlt)