[백준] 15650 N과 M(2)

문제 출처 : https://www.acmicpc.net/problem/15650

정답 코드 💻

import sys
input = sys.stdin.readline

n,m = map(int,input().split())

s = []

def dfs(start) :
    if len(s) == m :
        print(' '.join(map(str,s)))

    for i in range(start,n+1) :
        if i not in s :
            s.append(i)
            dfs(i+1)
            s.pop()

dfs(1)

👉🏻 재귀함수로 백트래킹 기법을 사용하여 모든 조합을 구하면 된다.

설명

👉🏻 15649번과 동일하지만, start 변수가 추가된다.

기존에는 1부터 n까지 모든 숫자를 사용했지만 [2,1]과 같이 앞의 숫자가 뒤의 숫자보다 작은 경우를 제외하기 위해 start부터 n까지 숫자를 사용한다.

재귀함수를 호출할 때는 i를 이용하여 자신의 다음 숫자를 부른다.

느낀 점 ✏️

백트래킹 시작!