N과 M(1)

입력

첫째 줄에 자연수 N과 M이 주어진다.
N과 M은 1이상 8이하

출력

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다. 중복되는 수열은 여러번 출력하면 안되고, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

해결방법

이 문제는 2가지의 방법으로 풀 수 있다.
순열을 이용해서 푸는 방법과 백트래킹을 이용해서 푸는 방법이다.
순열을 콤비네이션과 다르게 순서에 상관있게 나타낼 수 있다.
그래서 N개중 M개의 숫자를 고르면 된다.
백트래킹을 이용해서 모든 경우의 수에 대해서 재귀적으로 탐색하면 된다.

코드

우선 순열을 이용해서 푸는 것은 아래와 같다.

import sys
from itertools import permutations

N, M = map(int, sys.stdin.readline().split())
array = [i + 1 for i in range(N)]  # 1 ~ N까지의 숫자를 가진 배
permu = list(permutations(array, M))  # M개 만큼 순열함수 사용
for item in permu:
    for num in item:
        print(num, end=' ')
    print()

백트래킹을 이용해서 푸는 것은 아래와 같다.

import sys

def backTracking(numList):  # 백트래킹 함수
    if len(numList) == M:  # 길이가 M과 같다면 탈출
        array.append(numList)  # 정답 배열에 삽입
        return
    else:
        for i in range(1, N + 1):
            if i not in numList:
                backTracking(numList + [i])  # 리스트 끝 요소에 붙이기


N, M = map(int, sys.stdin.readline().split())
array = []
for i in range(1, N + 1):  # 1 ~ N까지의 숫자 체크
    backTracking([i])

for item in array:
    for num in item:
        print(num, end = ' ')
    print()