[백준] 15650: N과 M (2) - python[파이썬]

15649 문제를 통해 백트래킹을 이해한 덕분에 중복만 허용하지 않도록 바꾸면 되어서 바로 풀 수 있었다.

조합을 이용한 코드

import sys, itertools
input = sys.stdin.readline

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

nCr = itertools.combinations(lst, M)
for i in nCr:
    print(*i)

• 당연히 문제의도는 이게 아니지만 내장함수를 이용해서도 풀 수 있다.

백트래킹 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
lst = []

def backtracking(i=1):
    if len(lst) == M:
        print(*lst)
        return
    
    for j in range(i, N+1):
        if j not in lst:
            lst.append(j)
            backtracking(j+1)
            lst.pop()

backtracking()

• bractracking안에서 또다시 backtracking을 호출해서 이를 시행할 때 for문을 i=1부터 시행하면 안 된다. 즉, 이미 넣은 원소를 다시 넣지 않도록 하기 위해 backtracking에 매개변수를 추가해 주고 해당 매개변수부터 for문을 돌도록 해주면 된다.

결과