[Backtracking] 15652 N과 M(4)

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

15652번: N과 M (4)

# 2022.12.30
import sys
input = sys.stdin.readline

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

answer = []
def backtracking(start):
    if len(answer)==m:
        print(' '.join(map(str, answer)))
        return

    for i in range(start, n+1):
        answer.append(i)
        backtracking(i)
        answer.pop()

backtracking(1)

1. n, m 입력받음

2. answer이라는 리스트에 수열 append와 pop

3. len(answer)이 원하는 값인 m이라면 print해줌 & return

4. start~n까지 비내림차순 수열로 append

• 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순

-> backtracking(i)로 해주어야 등호(=)도 포함시켜 수열을 저장할 수 있다