[백준] 15666 N과 M 12 (python 파이썬)

15666번: N과 M (12)

---

백트래킹 문제

---

아이디어

어차피 같은 숫자를 반복해서 사용해도 되므로, 문제에서 제공한 N개의 수에서 중복을 제거해 준다.

 

백트래킹을 활용해 문제를 해결하면 된다.

---

전체 코드

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

numList = sorted(list(set(numList))) # 중복 제거후 정렬
n = len(numList)
answer = list()
seq = []

def dfs(num, depth):
    if depth == M:
        print(" ".join(map(str, seq)))
        return

    for i in range(numList.index(num), n):
        seq.append(numList[i])
        dfs(numList[i], depth + 1)
        seq.pop()

dfs(numList[0], 0)

---

코드 설명

def dfs(num, depth):
    if depth == M:
        print(" ".join(map(str, seq)))
        return

    for i in range(numList.index(num), n):
        seq.append(numList[i])
        dfs(numList[i], depth + 1)
        seq.pop()

 

제공된 숫자들을 순회하며 길이가 M인 수열을 만들어준다. 

수열의 길이가 M이 되면 print로 바로 출력해 준다. 이전에 이미 리스트를 정렬해 놓아서 

출력 순서는 고려 안 해도 된다.