BrianaAI

안녕하세요.

백트래킹을 공부하고 싶은 사람 있으면

N과 M 시리즈부터 공부를 해야해요.

https://www.acmicpc.net/workbook/view/2052

여기 들어가면 시리즈가 있습니다.

1번부터 12번까지의 저의 풀이 남기겠습니다. :) 화잇팅

#1.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]
def DF(lst):
    if len(lst)==M:
        print(" ".join(map(str, lst)))
        return
    for i in range(1, N+1):
        DF(lst+[tmp[i]])
DF([])

#2.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]
v = [0]*(N+1)

def DF(lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return
    for i in range(1, N+1):
        if v[i] == 0:
            v[i] = 1
            DF(lst+[tmp[i]])
            v[i] = 0
DF([])

#3.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]
v = [0]*(N+1)

def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for i in range(s, N+1):
        if v[i] == 0:
            v[i] = 1
            DF(i, lst+[tmp[i]])
            v[i] = 0
DF(1, [])

#4.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]

def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for i in range(s, N+1):
        DF(i, lst+[tmp[i]])

DF(1, [])

#5.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
v = [0]*(N+1)

def DF(lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for idx, i in enumerate(arr):
        if v[idx] == 0:
            v[idx] = 1
            DF(lst+[arr[idx]])
            v[idx] = 0
DF([])

#6.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
v = [0]*(N)
def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        if v[i] == 0:
            v[i] = 1
            DF(i, lst+[arr[i]])
            v[i] = 0
DF(0, [])

#7.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
def DF(lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for i in range(len(arr)):
        DF(lst+[arr[i]])
DF([])

#8.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        DF(i, lst+[arr[i]])
DF(0, [])

# 9.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ll = []
v = [0]*N
def DF(lst):
    if len(lst) == M:
        if lst not in ll:
            print(" ".join(map(str, lst)))
            ll.append(lst)
        return
    for i in range(len(arr)):
        if v[i] == 0:
            v[i] = 1
            DF(lst+[arr[i]])
            v[i] = 0
DF([])

#10.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
v = [0]*N
ll = []

def DF(s, lst):
    if len(lst) == M:
        if lst not in ll:
            ll.append(lst)
            print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        if v[i] == 0:
            v[i] = 1
            DF(i, lst+[arr[i]])
            v[i] = 0
DF(0, [])

# 11.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ll = []

def DF(lst):
    if len(lst) == M:
        if lst not in ll:
            print(" ".join(map(str, lst)))
            ll.append(lst)
        return
    for i in range(len(arr)):
        DF(lst+[arr[i]])
DF([])

#12.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ll = []
def DF(s, lst):
    if len(lst) == M:
        if lst not in ll:
            ll.append(lst)
            print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        DF(i, lst+[arr[i]])
DF(0, [])