[백준] 2309 일곱 난쟁이

https://acmicpc.net/problem/2309 

2309번: 일곱 난쟁이

dwarf = [int(input()) for _ in range(9)]
visited = [0] * 9
real_dwarf = []

def backtrack(index, total, vis_idx, arr, visit):
    if index == 7 and total == 100:
        real_dwarf.append([dwarf[i] for i in range(9) if visit[i]])
        return
    elif index > 7 or total > 100:
        return
    else:
        for i in range(vis_idx + 1, 9):
            if visit[i] == 0:
                visit[i] = 1
                backtrack(index + 1, total + arr[i], i, arr, visit)
                visit[i] = 0


backtrack(0, 0, -1, dwarf, visited)
print('\n'.join(map(str, sorted(real_dwarf[0]))))

재귀 백트래킹 방식으로 풀었다. 

사실 반쪽짜리 풀이인 것이 백트래킹을 했을 때 Prunning(가지치기) 하고, 답을 구했을때 함수를 끝내야하는데 제대로 하지 못하였다.

가지치기는 visit을 두어서 갔는지 확인하는걸로 했지만, 답을 구한경우에도 나머지 해도 다 돌게 된다.

아직 백트래킹은 어렵다...