백준 알고리즘 15650 (N과 M(2)) - python (재풀이)

백준 알고리즘 15650 (N과 M(2)) - python (재풀이)

> https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

오랜만에 다시 하니까 헷갈린다...!

중복 없이, 오름 차순 문제!

 

[문제 풀이]

1. N의 index가 헷갈리지 않게 N+1의 자연수화

2. 탈출 조건 depth == M 설정

3. 이전 자릿수보다 크게 되도록 for문에서 i+1 설정

4. 배열에 append 하면서 백트래킹

 

import sys

def DFS(depth, i):
    if depth == M: # 탈출 조건
        print(' '.join(map(str, result)))
        return
    else:
        for j in range(i+1, N+1):  # 이전 자릿수보다 크게
            if not visited[j]:
                visited[j] = True
                result.append(j)
                DFS(depth+1, j)  # 다음 자릿수로
                visited[j] = False  # 백트래킹
                result.pop()  # 백트래킹
    return

N, M = map(int, sys.stdin.readline().split())
visited = [False] * (N + 1)  # 자연수화
result = []

DFS(0, 0)