Combinations

Question

https://leetcode.com/problems/combinations/?tab=Description

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],
]

Tags

• backtracking

Thought

This is a backtracking problem. Here is the introduction to the backtracking algorithm: http://algorithms.tutorialhorizon.com/introduction-to-backtracking-programming/.

The start of the problem is: k = k. We selected a specific path when k = k in the for loop from 1 to n, and the rest of the problem is 2 to n until the end or k = 0. Push each correct solution into the result and restart with a new solution.

Code

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        def helper(n, start, k, result, item):
            for i in xrange(start, n - k + 2):
                if k == 1:
                    result.append(item + [i])
                else:
                    helper(n, i + 1, k - 1, result, item + [i])
            return result

        return helper(n, 1, k, [], [])