Combinations

Problem: Combinations

Different from other problems, we solve this problem by stack not recursion. Actually for most backtracking problems, either stack or recursion can be used.

Code in Python:

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        ans = []
        stack = []
        x = 1
        while True:
            if len(stack) == k:
                ans.append(stack[:])
            if len(stack) == k or x > n-k+1+len(stack):
                if not stack:
                    return ans
                x = stack.pop() + 1
            else:
                stack.append(x)
                x += 1

At every pushing, we try number from the smallest to biggest. If the stack's length meets the requirement, then we add the stack to the results and pop the top number to try numbers bigger than it. If there is no more potential number to be pushed, then we pop the top number to try other numbers at situation. We continue doing so until there is no more number can be pushed into the first position of the stack, that means we iterate through all the solutions.