문제 15650

풀이

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

N과 M 시리즈

백트래킹 문제
arr: 수열이 담긴 리스트

1. func(start)
   start을 통해 오름차순으로 수열을 뽑을 수 있다.
2. if i not in arr: 이 코드 없어도 정답
   왜냐하면, func(i+1)이어서 그 전으로 갈 일 없음

참고: ' '.join(map(str, arr))
arr을 str로 바꾸고 join을 이용하여 원소 사이 공백 한 칸으로 구분하여 출력

정답

import sys
input = sys.stdin.readline

def func(start):
    if len(arr)==M:
        print(' '.join(map(str,arr)))
        return

    for i in range(start,N+1):
        if i not in arr: # 중복제거
            arr.append(i)
            func(i+1) # 현재 다음 숫자부터 수열에 들어감
            arr.pop()
            
N, M = map(int, input().split())
arr = []
func(1) # 1부터시작

제출