combinations

class (object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(n, k, [], res, 1)
        return res
        
    def dfs(self, n, k, cur, res, pos):
        if len(cur) == k:
            res.append(cur[:])
            return
        
        for i in range(pos, n+1):
            if i in cur:
                continue
            cur.append(i)
            self.dfs(n, k, cur, res, i+1)
            cur.pop()

class (object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        
        ans = []
        stack = []
        x = 1
        while True:
            l = len(stack)
            if l == k:
                ans.append(stack[:])
            if l == k or x > n - k + l + 1: 
                # n - x + 1 < k - l, there is not enough big numbers to insert into the current stack
                # n - x + 1 剩下的数的个数
                # l 当前在栈里的数的个数
                # k 要求的长度
                if not stack:
                    return ans
                # x 的值更新为最后一个值加1 "123" -> "124" -> "125" -> "13"
                x = stack.pop() + 1
            else:
                stack.append(x)
                x += 1

class (object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        if k==1:
            return [[i] for i in range(1,n+1)]
        elif k==n:
            return [[i for i in range(1,n+1)]]
        else:
            rs=[]
            rs+=self.combine(n-1,k) # 不包含最后一个数n
            part=self.combine(n-1,k-1) # 包含最后一个数n
            for ls in part:
                ls.append(n)
            rs+=part
            return rs