[77] Combinations

https://leetcode.com/problems/combinations/description/

• algorithms
• Medium (44.47%)
• Source Code: 77.combinations.py
• Total Accepted: 195.1K
• Total Submissions: 415.5K
• Testcase Example: '4\n2'

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2 Output: [ [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 = []
        if k > n: return result

        pool = list(range(1, n+1))

        self.helper(pool, result, [], k)

        return result

    def helper(self, pool, result, current, k):
        if len(current) == k:
            result.append(current)
            return

        release = [i for i in pool if i not in current]
        for it in release:
            if not current or it > current[-1]:
                self.helper(pool, result, current[:] + [it], k)


s = Solution()
print s.combine(20, 16)