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

https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3 

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

 

Fact Finding

---

• 재귀 함수를 통한 DFS 구현
• '+'와 '-'를 번갈아서 적용해주어 모든 경우의 수를 check
• 이 중 타겟 넘버와 일치할 때 +1 증가시키고 recursion 수행

Time Complexity

---

• 최악의 경우 O(n^2)로 판단되는 데 정확히 분석한 것인지 확실하지 않음

 

def problem(arr, target, ans, i, sums = 0) : 
    if i == len(arr) : 
        sums = sum(arr)
        if (sums == target) : 
            ans += 1
        return ans
    i += 1
    ans = problem(arr, target, ans, i)
    i -= 1
    arr[i] = -arr[i]
    i += 1
    ans = problem(arr, target, ans, i)
    return ans
def solution(numbers, target):
    ans = 0; i = 0;
    answer = problem(numbers, target, ans, i)
    return answer