[Leetcode] 77. Combinations

🔗 Problem Link

Combinations - LeetCode

---

❔Thinking

• 1부터 n까지의 숫자들 가운데 k개를 뽑아 조합한 결과를 반환한다.

---

💻Solution

1. 조합을 활용한 풀이

from itertools import combinations
def combine(self, n: int, k: int):
    n_list = [i for i in range(1,n+1)]
    return list(combinations(n_list, k))

 

2. DFS을 활용한 풀이

def combine(self, n: int, k: int):
    nums = [i for i in range(1, n+1)]
    result = []
    stack = [[0, nums, []]]
    while stack:
        length, integers, ans = stack.pop()
        if length == k:
            result.append(ans)
        else:
            for i in range(len(integers)):
                stack.append([length+1, integers[i+1:], ans+[integers[i]]])
    return result

---

🗝️keypoint

1. DFS를 활용할 때, [1,2] 와 [2,1]를 하나로 합치기 위한 sort나 set()은 시간초과가 발생한다.