class Solution:

    def combine(self, n: int, k: int) -> List[List[int]]:

        res = []

        def backtrack(i,temp_list):

            if len(temp_list)==k:

                res.append(temp_list)

            for j in range(i,n+1):

                backtrack(j+1,temp_list+[j])

        backtrack(1,[])

        return res

class Solution:

    def combine(self, n: int, k: int) -> List[List[int]]:

        nums = list(range(1, k + 1)) + [n + 1]

        output, j = [], 0

        while j < k:

            output.append(nums[:k])

            j = 0

            while j < k and nums[j + 1] == nums[j] + 1:

                nums[j] = j + 1

                j += 1

            nums[j] += 1

        return output