리트코드 77번 combinations (python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Solution

DFS

from typing import List
from itertools import combinations

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        answer = []
        def dfs(i, n_list: List[int]):
            if len(n_list) == k:
                answer.append(n_list)

            for j in range(i+1, n+1):
                dfs(j, n_list + [j])

        for i in range(1, n+1):
            dfs(i, [i])

        return answer

조합의 경우 순열과 달리 (1, 4), (4, 1)을 같은 것으로 본다. 따라서, 자신보다 큰 수들만 탐색하도록 dfs를 구현하였다.

itertools

from typing import List
from itertools import combinations

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(map(list, combinations([i+1 for i in range(n)], k)))

Reference

파이썬 알고리즘 인터뷰 35번