77 조합

77 조합

문제

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.

• n: n까지의 숫자
• k: k개의 조합
• 순서 무관

조건

• $1 \le n \le 20$
• $1 \le k \le n$

예제

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

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

해결

1st

1 생각

• 조합?
  • 여러 물건 중에서 일부 또는 전부를 꺼내는 경우의 수
  • {1, 2, 3}에서 2개를 꺼내는 경우는 {1,2},{2,3},{1,3}이며, {1,2}와 {2,1}은 같다
  • 순서 없는 순열
• 한 번 뽑았으면 다시 뽑을 필요 없다.

1 코드

# https://leetcode.com/problems/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.
'''
from typing import *
import collections

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        numbers = [i for i in range(1, n + 1)]

        def dfs(numbers, combination, depth):
            # 조합하려는 k개가 완성되면 종료
            if len(combination) == k:
                ans.append(combination)
                return
            
            # 숫자들을 비워 나간다
            while numbers:
                number = numbers.pop(0)
                # 참조로 넘어가지 않도록 새로운 배열 생성하여 전달
                dfs(numbers[:], combination + [number], depth + 1)

        dfs(numbers, [], 0)
        return ans

s = Solution()

print(s.combine(4, 2))
print(s.combine(5, 3))

1 결과: 성공

27 / 27 test cases passed. Status: Accepted
Runtime: 528 ms
Memory Usage: 15.7 MB

2nd

2 itertools

• itertools를 쓰면 훨씬 빠르다
• python 아닌 C 언어로 짜여 있기 때문인 듯하다

2 코드

import itertools

def combine2(self, n: int, k: int) -> List[List[int]]:
    return list(itertools.combinations([i for i in range(1, n + 1)], k))