[백준] 15654 N과 M(5) (python 파이썬)

https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

---

아이디어

1. 백트래킹

• 이미 N과 M 문제를 풀어봐서 바로 떠올랐다.
• 깊이가 M이 될 때마다 주어진 숫자들을 탐색하면 된다.
• 이 문제에서는 순열, 중복되지 않은 숫자들을 나열해야 하므로 이미 추가된 숫자가 있으면 continue로 넘겨준다.

---

전체 코드

N, M = map(int, input().split())
numbers = [int(x) for x in input().split()]

numbers.sort()

def backtracking(depth):
    if depth == M:
        print(' '.join(map(str,box)))
        return

    for i in range(N):
        if numbers[i] in box:
            continue
        box.append(numbers[i])
        backtracking(depth + 1)
        box.pop()

box = []
backtracking(0)

---

코드 설명

numbers.sort()

def backtracking(depth):
    if depth == M:
        print(' '.join(map(str,box)))
        return

    for i in range(N):
        if numbers[i] in box:
            continue
        box.append(numbers[i])
        backtracking(depth + 1)
        box.pop()

box = []
backtracking(0)

 

오름차순으로 정렬되어있는 숫자 순서대로 숫자를 탐색한다. 

그리고 빈 리스트(box)를 사용해 숫자를 넣어준다.

이미 넣은 숫자면 continue를 사용해 다음 숫자로 넘어간다.

 

수열의 길이가 M이 되면(depth == M) box리스트에 있는 수열을 출력해주고 return 한다.

return후 넣었던 숫자를 다시 빼주면 된다.