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

타겟 넘버

문제 링크

나의 풀이

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    def dfs(idx, result):
        if idx == n:
            if target == result:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])

    dfs(0, 0)

    return answer

• 재귀를 이용한 DFS를 적용하여 풀이하였다. 처음 인덱스와 결과 값을 각각 0으로 설정하고 한번 순환할 때마다 다음 노드로 넘어가는 방식이다.
• 인덱스 값과 numbers의 len값이 같을때 target과 result 값이 같으면 answer가 1이 올라간다.
  👉 이때 nonlocal 변수 answer를 선언해줘야 하는데 nonlocal과 global의 쓰임에 대해서는 추가적으로 글 작성을 하도록 하겠다.

다른사람의 풀이

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

• 또 다른 재귀의 방식으로 풀이 한 것이다. 생각하지 못한 방식이라 가져와봤다.