[매일알고] 타겟넘버

주어진 숫자를 더하거나 빼서 타겟 넘버를 만드는 방법의 수를 return 하는 함수

 

[풀이 1] 2진법 이용

각 숫자 앞에 들어갈 연산을 2진수로 나타낸다. ( + 는 1, - 는 0)

Numbers 의 길이에 따라서 연산의 경우의 수는 2의 n승 (n= numbers의 길이)

예를 들어, numbers 가 123 으로 주어진다면 연산의 경우의 수는 2^3 = 8 개가 될 것이다.

2진수 i in range (1, 8)	연산	sum
000	-1-2-3	-6
001	-1-2+3	0
010	-1+2-3	-2
011	-1+2+3	4
100	1-2-3	-4
101	1-2+3	2
110	1+2-3	0
111	1+2+3	6

 

[풀이 2] 재귀함수 이용

 

 

예를 들어, numbers가 123으로 주어진다면

Len(nums) = 3 -> i=3이 될때 까지 아래의 알고리즘을 반복하게 된다. 

I=3 이 되면, n의 값이 타겟넘버와 같은지 확인하고, 같다면 1을 return한 뒤 , ret의 값을 모두 더하면 타겟넘버가 되는 경우의 수가 된다.