77. Combinations

문제

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

You may return the answer in any order.

예시

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
Example 2:

Input: n = 1, k = 1
Output: [[1]]

풀이

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        nums = [i for i in range(1, n+1)]
        res = []
        def generate(chosen):
            if len(chosen) == k:
                res.append(chosen[:])
                return

            start = nums.index(chosen[-1]) + 1 if chosen else 0
            for nxt in range(start, len(nums)):
                chosen.append(nums[nxt])
                generate(chosen)
                chosen.pop()

        generate([])
        return res 

문제에서 알 수 있듯이, 주어진 input의 k개 조합을 구하는 문제로, itertools의 combinations과 같은 결과를 요구한다.

itertools.combinations( [i for i in range(1, n+1)], k )

조합의 특징 중 하나로는 집합의 성격을 띄고 있다. 즉, 개수에 맞게 이뤄진 조합의 기준이 정해지면 나머지 원소들을 돌아가면서 조합을 생성해주면 된다.

k가 2라고 했을 때, nums = [1, 2, 3, 4, 5 ....n] 라고 하게 되면, 먼저 기준을 1 로 정할 수 있다. 1 로 정하게 되면 2 ~ n 까지의 원소를 append와 pop으로 돌아가면서 1과 조합을 만들어주면된다. 여기서 start는 다음 기준인 2에서는 1과의 조합이 필요없기 때문에 3 ~ n까지의 원소로 만들어주기 위함이다.