백트래킹 연습 : N과 M 모아보기

N과 M 시리즈

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

N과 M (1)

def dfs(num, lst):
    if len(lst) == m:
        print(*lst)
        return

    for k in range(1, n + 1):
        if not used[k] and k not in lst:
            used[k] = True
            dfs(k, lst + [k])
            used[k] = False


n, m = map(int, input().split())
used = [False] * (n + 1)
dfs(0, [])

N과 M (2)

def dfs(num, lst):
    if len(lst) == m:
        print(*lst)
        return

    for k in range(1, n + 1):
        if not used[k] and (not lst or k > lst[-1]):
            used[k] = True
            dfs(k, lst + [k])
            used[k] = False


n, m = map(int, input().split())
used = [False] * (n + 1)
dfs(0, [])

N과 M (3)

def dfs(num, lst):
    if len(lst) == m:
        print(*lst)
        return

    for k in range(1, n + 1):  # 중복 허용 -> used 체크 안해도 .. !
        dfs(k, lst + [k])


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

N과 M (4)

def dfs(num, lst):
    if len(lst) == m:
        print(*lst)
        return

    for k in range(1, n + 1):
        if not lst or k >= lst[-1]:
            dfs(k, lst + [k])


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

N과 M (5)

def dfs(idx, cur_arr):
    if len(cur_arr) == m:
        print(*cur_arr)
        return

    for i in range(n):
        if not used[i]:
            used[i] = True
            dfs(i, cur_arr + [arr[i]])
            used[i] = False


n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

used = [False] * n
dfs(0, [])

N과 M (6)

def dfs(idx, cur_arr):
    if len(cur_arr) == m:
        print(*cur_arr)
        return

    for i in range(idx, n):
        if not cur_arr or arr[i] > cur_arr[-1]:
            dfs(i, cur_arr + [arr[i]])


n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

dfs(0, [])

N과 M (7)

def dfs(idx, cur_arr):
    if len(cur_arr) == m:
        print(*cur_arr)
        return

    for i in range(n):
        dfs(i, cur_arr + [arr[i]])


n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

dfs(0, [])

N과 M (8)

def dfs(idx, cur_arr):
    if len(cur_arr) == m:
        print(*cur_arr)
        return

    for i in range(idx, n):
        dfs(i, cur_arr + [arr[i]])


n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

dfs(0, [])

N과 M (9)

def dfs(idx, cur_arr):
    if len(cur_arr) == m:
        if tuple(cur_arr) not in v:
            v.add(tuple(cur_arr))
            print(*cur_arr)
        return

    for i in range(n):
        if not used[i]:
            used[i] = True
            dfs(i, cur_arr + [arr[i]])
            used[i] = False


n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

used = [False] * n
v = set()
dfs(0, [])

N과 M (10)

def dfs(idx, cur_arr):
    if len(cur_arr) == m:
        if tuple(cur_arr) not in v:
            v.add(tuple(cur_arr))
            print(*cur_arr)
        return

    for i in range(n):
        if not used[i] and (not cur_arr or arr[i] >= cur_arr[-1]):
            used[i] = True
            dfs(i, cur_arr + [arr[i]])
            used[i] = False


n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

used = [False] * n
v = set()
dfs(0, [])

N과 M (11)

def dfs(idx, cur_arr):
    if len(cur_arr) == m:
        if tuple(cur_arr) not in v:
            v.add(tuple(cur_arr))
            print(*cur_arr)
        return

    for i in range(n):
        dfs(i, cur_arr + [arr[i]])


n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

v = set()
dfs(0, [])

N과 M (12)

def dfs(idx, cur_arr):
    if len(cur_arr) == m:
        if tuple(cur_arr) not in v:
            v.add(tuple(cur_arr))
            print(*cur_arr)
        return

    for i in range(idx, n):
        dfs(i, cur_arr + [arr[i]])


n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

v = set()
dfs(0, [])