[프로그래머스][Python3] 타겟 넘버

문제 :

https://programmers.co.kr/learn/courses/30/lessons/43165

나의 풀이 :

def solution(numbers, target):

    def dfs(target, remain, visit, end):

        if abs(target) <= remain:

            if visit == end:

                if abs(target) == remain:

                    nonlocal ans

                    ans += 1

            else:

                num = numbers[visit]

                dfs(target+num, remain-num, visit+1, end)

                dfs(target-num, remain-num, visit+1, end)

    numbers = sorted(numbers, reverse=True)

    ans = 0

    dfs(target, sum(numbers), 0, len(numbers)-1)

    return ans

한마디 :

모든 경우의 수를 탐색하기에 앞서 가지치기를 위해 역순 정렬을 먼저 해두었다. 큰 수부터 먼저 처리를 해야 나머지 경로를 추가 탐색할 가치가 있는지 빠르게 판단할 수 있다.