def combinations(n, k):
    output, path = [], []
    def visit(start):
        need = k - len(path)
        if need == 0:
            output.append(path.copy())
            return
        for value in range(start, n - need + 2):
            path.append(value)
            visit(value + 1)
            path.pop()
    visit(1)
    return output