LC77 Combinations

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.res = []
        # if n<=0 or k <=0  or k>n:
        #     return res 
        self._dfs(1,k,n,[])
        return self.res 
    def _dfs(self,start, k, n, pre):
        if len(pre) == k:
            self.res.append(pre[:])
            return 
        for i in range(start,n+1):
            pre.append(i)
            self._dfs(i+1,k,n,pre)
            pre.pop()  # clear out pre stack for next loop
            

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.res = []
        # if n<=0 or k <=0  or k>n:
        #     return res 
        self._dfs(1,k,n,[])
        return self.res 
    def _dfs(self,start, k, n, pre):
        if len(pre) == k:
            self.res.append(pre[:])
            return 
        for i in range(start,n-(k-len(pre)-1)+1):
            pre.append(i)
            self._dfs(i+1,k,n,pre)
            pre.pop()  # clear out pre stack for next loop
            

from itertools import combinations
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(combinations(range(1,n+1),k))