[프로그래머스] 타겟 넘버 _파이썬

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

재귀로 풀려고 시도했는데 실패.. 거의 다 왔는데 조금만 더 고민해볼걸. 아래 풀이는 다른 분들 풀이 참고했음.

방법1. tree 이용

• 반복문 돌면서 이번에 계산된 값이 이전 값의 서브트리가 되도록 하는 방법

def solution(numbers, target):
    tree = [0]
    for num in numbers:
        subtree = []
        
        for leaf in tree:
            subtree.append(leaf+num)
            subtree.append(leaf-num)
        tree = subtree
    
    return tree.count(target)

방법2. dfs 이용

• idx가 끝까지 갈 때 까지 재귀 호출하면서 확인

def dfs(idx, numbers, target, value):
    global answer

    if idx == len(numbers) and value == target:
        answer += 1
        return
    if idx == len(numbers):
        return

    dfs(idx+1, numbers, target, value + numbers[idx])
    dfs(idx+1, numbers, target, value - numbers[idx])

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

방법3. 천재적인 재귀 사용

-> 프로그래머스 풀이 중 가장 좋아요 수 많은 풀이

• solution 함수 자체로 재귀를 돌림
• 위에서 풀었던 dfs 방법과 같은 원리
• target 값 자체에 계산을 해줌으로써 target == 0이라는 건 계산 결과가 곧 target 값과 같다는 것을 의미

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