[Baekjoon]백준 15651 N과 M (3)(실버 3) - Python

문제설명

예제2

예제3

문제를 살펴보면 이전 문제들과 다르게 이번에는 중복된 숫자도 처리해야한다

def generate_sequences(num, length):
    result = []
    def backtrack(curr_seq, start):
        if len(curr_seq) == length:
            result.append(curr_seq.copy())
            return
        for i in range(start, num+1):
            if i not in curr_seq:
                curr_seq.append(i)
                backtrack(curr_seq, i+1)
                curr_seq.pop()

    backtrack([], 1)
    return result

num, length = map(int, input().split())
sequences = generate_sequences(num, length)
for res in sequences:
    print(*res)

이는 이전에 풀이한 문제의 코드인데, 이 문제를 풀기 위해 if문을 삭제하고 start부분을 삭제해야한다

if문이 존재하기때문에 중복을 출력하지 않았고, start로 인해 2 3 과 같은 조합만 출력하였기 때문이다

def generate_sequences(num, length):
    result = []
    def backtrack(curr_seq):
        if len(curr_seq) == length:
            result.append(curr_seq.copy())
            return
        for i in range(1, num+1):
            curr_seq.append(i)
            backtrack(curr_seq)
            curr_seq.pop()

    backtrack([])
    return result

num, length = map(int, input().split())
sequences = generate_sequences(num, length)
for res in sequences:
    print(*res)

if문을 삭제하고 start부분을 삭제한 코드이다

단계별로 풀어보기에서 N과 M (1)부터 풀어왔다면 간단하게 해결가능한 문제이다