[알고리즘] 더하거나 빼거나 - ItisFuture

 Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 , 타겟 넘버 target_number이 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오. - 리스트의 순서를 바꾸는 것이 아닌 순차적으로 더하거나 빼거나

cnt = 0
def plus_or_minus(num_list, target_num, start_idx, now_total):
	global cnt
	if start_idx == len(num_list):
    	if now_total == target_num:
        	cnt += 1
        return
    plus_or_minus(num_list, target_num, start_idx+1, now_total + num_list[start_idx])
    plus_or_minus(num_list, target_num, start_idx+1, now_total - num_list[start_idx])
plus_or_minus(num_list, target_num, 0, 0) # 처음 인덱스 = 0, 처음 총 합 = 0

각 값들이 -일 경우 +일 경우 두 가지로 나눠서 생각해줘야한다.

총경우의 수

len(num_list)**2

음이 아닌 정수라면 0도 포함일 것이기에

zero_cnt = num_list.count(0)
cnt = cnt/2**zero_cnt

재귀..재밌다.