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

---

문제설명

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

코딩테스트 연습 - 타겟 넘버

사고과정

• 주어진 numbers 중에 len(numbers) 개수 만큼 순열 경우의 수를 완전탐색하는 DFS를 활용하는 문제였다.
• 단, 상태트리를 만들 때, 특정 수를 더해주거나 빼줄지 두 갈래길로 뻗어나가도록 해주어야 한다. 그리고 백트래킹할 경우에는 해당 인덱스 숫자에 -를 붙여서 res 리스트에 첨가해주면 된다. 그리고 트리 깊이가 len(numbers)에 다다르면 그 때, res의 원소를 sum 해준 뒤 그것이 target 값과 동일하면 카운트해주면 된다!

풀이

def solution(numbers, target):
    n = len(numbers)
    res = [0] * n
    count = 0
    
    def dfs(L):
        nonlocal count
        if L == n:
            if sum(res) == target:
                count += 1
            return
        else:
            res[L] = numbers[L]
            dfs(L+1)
            res[L] = -numbers[L]
            dfs(L+1)
    
    dfs(L=0)
    return count