combinations.py

# source: https://leetcode.com/problems/combinations/

class Solution(object):
    def combine(self, n, k):
        output = []
        stack = []
        i = 1
        length = 0
        while True:
            # if stack if k long, add to solution (as copy)
            if length == k: 
                output.append(stack[:])

            # if done with stack or out of options...
            if length == k or i > (n - k + length + 1):
                if length == 0: # no more options!
                    return output
                # BACKTRACK
                i = stack.pop() + 1 # remove tail end and focus on next number
                length -= 1
            else:
                # stack needs more options
                stack.append(i)
                i += 1
                length += 1