Python
파이썬 알고리즘 인터뷰 - 35. 조합
s코딩초보s
2022. 1. 30. 14:18
<--- 리트코드 77. Combinations --->
# 문제: 전체 수 n을 입력받아 k개의 조합을 리턴하라.
입력
n = 4, k = 2 |
출력
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4] ] |
# 풀이
1. DFS로 k개 조합 생성
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def combine(n, k):
results = []
def dfs(elements, start, k):
if k == 0:
results.append(elements[:])
for i in range(start, n + 1):
elements.append(i)
dfs(elements, i + 1, k -1)
elements.pop()
dfs([], 1, k)
return results
n = 4
k = 2
print(combine(n, k))
|
cs |
2. itertools 모듈 사용
1
2
3
4
5
6
7
8
9
|
import itertools
def combine(n, k):
return list(itertools.combinations(range(1, n + 1), k))
n = 4
k = 2
print(combine(n, k))
|
cs |