Combinations

题目描述

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

解题方法

对于combination，不同顺序是同一combination,所以应该采用subsets的方法， 在途中判断当前list的长度

Solution

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        results = []
        if not n:
            return []
        self.subsetsHelper(results, n, k, 1, [])
        return results

    def subsetsHelper(self, results, n, k, index, curList):
        if len(curList) == k: 
            tmpList = list(curList)
            results.append(tmpList)

        for i in range(index, n + 1):
            curList.append(i)
            self.subsetsHelper(results, n, k, i + 1, curList)
            curList.pop()

Reference