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

문제

숫자 배열과 타겟 넘버가 주어질 때, 숫자 배열의 순서를 바꾸지 않고 각 숫자를 더하거나 빼서 타겟 넘버를 만들 수 있는 경우의 수를 구하는 문제

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

프로그래머스

• 알고리즘 분류 - 깊이/너비 우선 탐색 (DFS, BFS)
• 난이도 - Level 2

---

접근 방법

백트래킹을 사용하여 숫자 하나하나마다 그 수를 더하는 경우와 빼는 경우로 가지를 뻗었고, 각 경우에 대한 계산 결과를 누적시켰다.

---

답안 코드

+2

answer = 0

def dfs(numbers, idx, visited, s, t):
    global answer
    
    # 배열 내 모든 수를 한 번 씩 써서 수식을 만들었으면 재귀 탈출
    if len(visited) == len(numbers):
        if s==t: # 수식 결과가 원하던 결과값이면 답+1
            answer += 1
        return
        
    # DFS & 백트래킹
    visited.append(idx)
    s += numbers[idx] # 더하는 경우
    dfs(numbers, idx+1, visited, s,t)
    s -= numbers[idx] * 2 # 빼는 경우
    dfs(numbers, idx+1, visited, s,t)
    visited.pop()
    

def solution(numbers, target):
    global answer
    
    dfs(numbers, 0, [], 0, target)
    
    return answer