알고리즘 오답노트 05

더하거나 빼거나

• 틀린 부분 : 전체 반복문을 돌리려고 했으나, 재귀함수를 이용하면 훨씬 간단하다.
• 틀린 이유 : [2, 3, 1] +2와 -2 그 다음 인덱스에서 +3 -3 이렇게 두 경우의 수를 계속 가지치기 해나가면 되는데 이는 재귀함수로 표현할 수 있다.

numbers = [2, 3, 1]
target_number = 0
result_count = 0  # target 을 달성할 수 있는 모든 방법의 수를 담기 위한 변수

def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
  if current_index == len(array):  # 탈출조건!
    if current_sum == target:
      global result_count # 함수 내부에서 외부의 변수를 불러올때.
      result_count += 1  # 마지막 다다랐을 때 합계를 추가해주면 됩니다.
    return
  get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum + array[current_index])
  get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum - array[current_index])

get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0)
# current_index 와 current_sum 에 0, 0을 넣은 이유는 시작하는 총액이 0, 시작 인덱스도 0이니까 그렇습니다!
print(result_count)  # 2가 반환됩니다!

함수에서는 외부 변수에 대해 global 마킹을 통해 가져올 수 있음을 기억하자!