old_contents: # Time:  O(n!)
  # Space: O(n)
  #
  # Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
  # 
  # For example,
  # If n = 4 and k = 2, a solution is:
  # 
  # [
  #   [2,4],
  #   [3,4],
  #   [2,3],
  #   [1,2],
  #   [1,3],
  #   [1,4],
  # ]
  #
  
  class Solution:
      # @return a list of lists of integers
      def combine(self, n, k):
          result = []
          self.combineRecu(n, result, 0, [], k)
          return result
      
      def combineRecu(self, n, result, start, intermediate, k):
          if k == 0:
              result.append(intermediate[:])
              return
          for i in xrange(start, n):
              intermediate.append(i + 1)
              self.combineRecu(n, result, i + 1, intermediate, k - 1)
              intermediate.pop()
  
  if __name__ == "__main__":
      result = Solution().combine(4, 2)
      print result
  
new_contents: # Time:  O(k * C(n, k))
  # Space: O(k)
  
  # Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
  # 
  # For example,
  # If n = 4 and k = 2, a solution is:
  # 
  # [
  #   [2,4],
  #   [3,4],
  #   [2,3],
  #   [1,2],
  #   [1,3],
  #   [1,4],
  # ]
  
  class Solution(object):
      def combine(self, n, k):
          """
          :type n: int
          :type k: int
          :rtype: List[List[int]]
          """
          result, combination = [], []
          i = 1
          while True:
              if len(combination) == k:
                  result.append(combination[:])
              if len(combination) == k or \
                 len(combination)+(n-i+1) < k:
                  if not combination:
                      return result
                  i = combination.pop()+1
              else:
                  combination.append(i)
                  i += 1
          return result
      
  
  class Solution2(object):
      def combine(self, n, k):
          """
          :type n: int
          :type k: int
          :rtype: List[List[int]]
          """
          def combineDFS(n, start, intermediate, k, result):
              if k == 0:
                  result.append(intermediate[:])
                  return
              for i in xrange(start, n):
                  intermediate.append(i+1)
                  combineDFS(n, i+1, intermediate, k-1, result)
                  intermediate.pop()
  
          result = []
          combineDFS(n, 0, [], k, result)
          return result
  
  
  if __name__ == "__main__":
      result = Solution().combine(4, 2)
      print result
  
subject: Update combinations.py