공통
자연수 N과 M이 주어졌을 때 아래 조건을 만족하는 길이가 M인 수열을 모두 구하라

15649. N과 M(1)

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
사전순으로 증가

4 2 입력시 1 2, 1 3, 1 4, 2 1, 2 3, 2 4 ~ 출력

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
ans = []



def dfs(depth):
    if depth == m:
        print(*ans)
        return

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

dfs(0)

15650. N과 M(2)

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
오름차순

4 2 입력시 1 2, 1 3, 1 4, 2 3, 2 4 ~ 출력

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
visited = [False]*n
ans = [0]



def dfs(depth,idx):
    if depth == m:
        print(*ans[1:])
        return

    prev_num = ans[-1]
    for i in range(idx,n+1):
        if i not in ans and i>prev_num:
            ans.append(i)
            dfs(depth+1, idx+1)
            ans.pop()




dfs(0,1)

15651. N과 M(3)

1부터 N까지 자연수 중에서 중복 가능 M개를 고른 수열
사전 순
4 2 입력시 1 1, 1 2, 1 3, 1 4, 2 1, 2 2, 2 3, 2 4 ~ 출력

import sys
input = sys.stdin.readline

n,m = map(int,input().split()) 
ans = []

def back():
    if len(ans) == m:
        print(*ans)
        return

    for i in range(n):
        ans.append(i+1)
        back()
        ans.pop()

back()

15652. N과 M(4)

1부터 N까지 자연수 중에서 중복 가능 M개를 고른 수열
비내림차순 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK
4 2 입력시 1 1, 1 2, 1 3, 1 4, 2 2, 2 3, 2 4 ~ 출력

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
ans = [0]


def dfs(depth):
    if depth == m:
        print(*ans[1:])
        return

    prev = ans[-1]
    for i in range(1,n+1):
        if i>= prev:
            ans.append(i)
            dfs(depth+1)
            ans.pop()




dfs(0)