[알고리즘] 백트래킹 기본 예제 코드(순열, 조합)

백트래킹으로 순열, 조합 구하기

백트래킹은 탐색 과정에서 불필요한 경로를 미리 차단하여 효율적으로 해를 찾는 기법인데요. 이를 활용하면 순열과 조합을 생성할 때, 가능한 모든 경우를 탐색하면서도 불필요한 연산을 줄일 수 있습니다. 

 

순열 (같은 수 중복 X)

n, m = map(int, input().split())
arr = [x for x in range(1, n+1)]
result = [0] * m
visited = [False] * n

def func(k):
    if k == m:
        print(*result)
        return

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            result[k] = arr[i]
            func(k+1)
            visited[i] = False

func(0)

 

조합  (같은 수 중복 X)

n, m = map(int, input().split())
arr = [x for x in range(1, n+1)]
visited = [False] * n
result = [0] * m

def func(k, st):
    if k == m:
        print(*result)
        return

    for i in range(st, n):
        if not visited[i]:
            visited[i] = True
            result[k] = arr[i]
            func(k+1, i+1)
            visited[i] = False

func(0, 0)

 

순열 (같은 수 중복 O)

n, m = map(int, input().split())
arr = [x for x in range(1, n+1)]
result = [0] * m

def func(k):
    if k == m:
        print(*result)
        return
    
    for i in range(n):
        result[k] = arr[i]
        func(k+1)

func(0)

 

조합 (같은 수 중복 O)

n, m = map(int, input().split())
arr = [x for x in range(1, n+1)]
result = [0] * m

def func(k, st):
    if k == m:
        print(*result)
        return
    
    for i in range(st, n):
        result[k] = arr[i]
        func(k+1, i)

func(0, 0)