조합(combination) 직접 구현해보기 in Python

파이썬에는 from itertools import combinations라는 내장함수가 있지만, 어떻게 작동하는지 알면 시간 복잡도 면에서도, 다른 문제를 풀 때 응용하기에도 좋을 것 같아서 직접 구현해보고자 했다. 

 

[방식1]

def get_comb(arr, n):
    combinations = []
    if n == 0:
        return [[]]
    for i in range(0, len(arr)):
        front = arr[i]
        back = arr[i+1:]
        for c in get_comb(back, n-1):
            combinations.append([front]+c)
    return combinations

[방식2]

def comb(population,num):
	ans = []
    ## 정의된 값인지 확인한다.
	if num > len(population): return ans
	## Base Case
	if num == 1:
		for i in population:
			ans.append([i])
    ## General Case
	elif num>1:
		for i in range(len(population)-num+1): ## i가 시작하는 값 = len(population) - (n-1)이고 이 때 n은 lst로부터 추출할 개수와 같다.
			for temp in comb(population[i+1:],num-1):
				ans.append([population[i]]+temp)

	return ans