[코드트리] Backtracking - K개 중에 1개를 N번 뽑기

문제

코드트리 학습하기 - 알고리즘 입문 : Backtracking

• K개 중에 1개를 N번 뽑기 (Python)
  https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition/description

코드 구현

# 1이상 ~ K이하 숫자를 하나 고르기 -> N번 반복하여 나오는 순서쌍 구하기

K, N = map(int, input().split())
answer = []

def pick_num(num):  # 지금까지 num개의 숫자를 뽑았을 때 그 다음 어떤 수를 뽑을지 선택
    # 종료 조건
    if (num == N):  # N만큼 뽑았다면 탈출
        print(*answer)
        return

    # 실행 조건
    for i in range(1, K+1):     # K 이하의 수 중 그 다음 수를 append
        answer.append(i)
        pick_num(num + 1)
        answer.pop()

    return


pick_num(0)

풀이

• 기본 개념 : https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition/introduction
  해설 : https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition/explanation
• num : 현재까지 뽑은 개수
• 0부터 시작해서 뽑은 개수가 N개라면 → 출력 (재귀 탈출)

ex) K = 2, N = 2
pick_num(0) 시작

해설 코드

# 변수 선언 및 입력
k, n = tuple(map(int, input().split()))
selected_nums = []

# 선택된 원소들을 출력해줍니다.
def print_permutation():
    for num in selected_nums:
        print(num, end = " ")
    print()

def find_permutations(cnt):
    # n개를 모두 뽑은 경우 답을 출력해줍니다.
    if cnt == n:
        print_permutation()
        return
    
    # 1부터 k까지의 각 숫자가 뽑혔을 때의 경우를 탐색합니다.
    for i in range(1, k + 1):
        selected_nums.append(i)
        find_permutations(cnt + 1)
        selected_nums.pop()

find_permutations(0)