순열과 조합을 구현해보자

순열과 조합

backtracking 을 이용한 조합

n, m = map(int, input().split())
data = []


def combination(pre_num):
    if len(data) == m:
        print(*data)
    else:
        for i in range(1, n+1):
            if pre_num < i:
                data.append(i)
                combination(i)
                data.pop()


combination(0)

순열

n, m = map(int, input().split())
data = []


def permutation(pre_list):
    if len(data) == m:
        print(*data)
    else:
        for i in range(1, n+1):
            if i not in pre_list:
                data.append(i)
                pre_list = data
                permutation(pre_list)
                data.pop()


permutation([])

 

 

백트래킹의 기본 구조를 익힐 수 있는 좋은 예제라고 생각합니다.

재귀로 구현하고 종료 조건을 명시합니다. 

가장 중요한 반복문에서 백트래킹에서 divide and conquer할 추상 단위를 추가한 후, 처리, 삭제를 반복합니다.

백트래킹의 대부분의 문제가 위 과정에서 벗어나지 않기 때문에 아예 외워버리는 것이 좋다고 생각합니다.