파이썬 알고리즘 인터뷰 - 35. 조합

 

<--- 리트코드 77. Combinations --->

# 문제: 전체 수 n을 입력받아 k개의 조합을 리턴하라.

 

입력

n = 4, k = 2

출력

[   [2,4],   [3,4],   [2,3],   [1,2],   [1,3],   [1,4] ]

 

 

# 풀이

1. DFS로 k개 조합 생성

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))

 

2. itertools 모듈 사용

import itertools
 
def combine(n, k):
  return list(itertools.combinations(range(1, n + 1), k))
 
n = 4
k = 2
 
print(combine(n, k))