[백준] 15664 N과 M (10) (실버2) / 백트래킹, 파이썬튜터

문제요약

나의 코드 및 설명

• 문제의 조건에서 수열은 '비내림차순'이어야 하고, '중복되는 수열을 여러 번 출력하면 안된다.'고 한다.
• 비내림차순의 조건을 충족시키기 위해, 함수의 변수로 for문의 시작점 위치를 갖는다. 따라서 방문처리도 따로 안해줘도 된다.
• 중복되는 수열을 여러 번 출력하면 안된다는 조건을 충족시키기 위해, flag 방식을 활용하였다. 각 함수를 호출하고 for문을 돌기 전 prev를 0으로 초기화 한다. 그 후, 만약 prev가 입력으로 주어진 숫자와 같지 않다면, prev를 입력으로 주어진 숫자로 갱신하고 하위 함수를 호출한다. 

def dfs(count, start, temp_list):
    if count == m:
        ans.append(temp_list)
        return
    if count == n:
        return
    
    prev = 0
    for i in range(start, n):
        if prev != num_list[i]:
            prev = num_list[i]
            dfs(count+1, i+1, temp_list+[num_list[i]])

n, m = map(int, input().split())
num_list = list(map(int, input().split()))
num_list.sort()
ans = []

dfs(0,0,[])
for i in ans:
    print(" ".join(map(str, i)))

리턴 시 상위 함수에서 사용하던 prev가 그대로 남아있다!