조합 알고리즘 파이썬

arr = [1,2,3,4,5]
visted = [False for i in range(5)]

def comb(arr,idx,cnt):
    if cnt ==0:
        for i in range(len(visted)):
            if visted[i] == True:
                print(arr[i],end=' ')
        print()
        return
    for i in range(idx,len(arr)):
        if visted[i] == True:
            continue

        visted[i] = True
        comb(arr,i,cnt-1)
        visted[i]= False

comb(arr,0,3)

 

시간복잡도 O(2^n)

해당 원소를 뽑는다 안뽑는다 라는 두가지 경우로 시간복잡도는 2^n이 됨

 

매개변수 idx 를 중점적으로 봐보면 for문이 idx를 기준으로 시작하는것을 알수 있다.

그리고 idx를 기준으로 visted를 True로 변경한뒤 comb를 재귀로 호출하고

마지막 cnt 가 0일경우 다 뽑았다고 판단하여 True인 visted에 대해서 arr을 출력한다.