[leetcode 2024/02/15] 77. Combinations

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

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

이번 문제의 경우 python에 내장되어 있는 combinations라는 것을 이용하면, 한 줄로 풀 수 있다.

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

from itertools import combinations

# 'ABCD'에서 2개의 요소로 만들 수 있는 모든 조합
print(list(combinations('ABCD', 2)))

# [1, 2, 3, 4]에서 3개의 요소를 선택하는 모든 조합
print(list(combinations([1, 2, 3, 4], 3)))

이렇게 첫 번째 인자로는 전체 요소를 넣어주고, 두 번째 인자로는 몇개의 요소를 선택하고 싶은지 적는다.

 

하지만, dfs로도 풀어보아야 재밌으니~ 이것으로도 풀어보았다.

 

이번 문제의 중요 포인트는 [1, 2] 와 [2, 1]은 같은 것을 의미한다는 것이다.

따라서 이런 중복적인 문제를 어떻게 해결할 수 있을까 고민하다가, dfs 함수로 list 정보를 넘길 때, 이미 연결되어 있는 값보다 큰 값만을 넘기도록 구성하고자 하였다.

 

즉,

1 -> 2, 3, 4

2 -> 3, 4

3 -> 4

4 ->

이런식으로 넘겨서 중복되지 않도록 구성하였다.

for i in range(len(material)):
	dfs(result + [material[i]], material[i+1:])
# 이전 숫자보다 큰 수를 대상으로만 연결되도록 함.

이렇게 구성해 주었다.

연결된 material[i] 보다 큰 list 들만 material[i+1:] 로 넘겨주었다.

 

2. 코드

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(result, material):
            if len(result) == k:
                res.append(result)
                return
            for i in range(len(material)):
                dfs(result + [material[i]], material[i+1:])
            # 이전 숫자보다 큰 수를 대상으로만 연결되도록 함.

        res = []
        dfs([], list(range(1, n+1, 1)))
        return res