[백트래킹] N과 M(4) (BOJ 15652번, 실버3)

문제

https://www.acmicpc.net/problem/15652

• 1부터 N까지의 숫자 중 중복하여 숫자를 골라 길이 M인 오름차순 수열을 만들어 출력하라.

풀이

• 백트래킹을 사용한다.
• N과 M(3)과의 차이는 수열 속 숫자들이 오름차순으로 정렬된다는 점이다. 따라서 재귀함수 사용해 배열의 값을 삽입할 때, 해당 숫자 이상의 숫자들만 삽입할 수 있도록 설정하였다.
• 매개변수를 사용해 현재 값을 back() 함수에 넘겨주어 해당 값부터 N까지의 값을 answer 배열에 추가하도록 한다.
• 마찬가지로 answer 배열에 가장 마지막에 들어온 값을 빼고, 해당 자리에 새로운 값을 삽입하면서 모든 경우의 수열을 완성한다.

코드

# N과 M(4)
# 1부터 N까지의 숫자 중 중복하여 숫자를 골라 길이 M인 오름차순 수열을 만들어 출력하라.

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

def back(start):
    if len(answer) == M:
        print(" ".join(map(str, answer)))
        return
    
    for i in range(start, N+1):
        answer.append(i)
        back(i)
        answer.pop()

back(1)

출력 결과

입력 : 3 3

출력