타겟 넘버

풀이

풀이르 하면서 음 어떻게 푸는지 바로 감이 왔다.
바로 visited와 함수를 생성하고, 풀이를 진행했다.
그런데 문제가 생겼는데 보니 프로그래머스의 방식이 함수 안에 함수인 중첩함수로 사용하다 보니, nonlocal이 필요했다.

그런 연유로 다음과 같은 코드를 생성할 수 있었다.

# n개의 음이 아닌 정수들
# 순서를 바꾸지 않고 결과를 적절히 더하거나 빼서 타겟 넘버를 만들기
#

def solution(numbers, target):
    result = 0
    N = len(numbers)
    
    def dfs(n, sum_v):
        # 외부 변수 수정을 위해 nonlocal 선언
        nonlocal result
        if n == N:
            if sum_v == target:
                result += 1
            return
        
        # numbers[n]을 더하는 경우
        dfs(n+1, sum_v + numbers[n])
        # numbers[n]을 빼는 경우
        dfs(n+1, sum_v - numbers[n])
        
    dfs(0, 0)
    
    return result

다른 사람 풀이

어... 뭐야 이거 solution 자체를 return??! 대단쓰

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])