Programmers / Target Number

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def solution(numbers, target):
    return addsub(numbers, 0, 0, target)

def addsub(numbers, depth, sum, target):
    # Check depth
    if depth == len(numbers):
        if target == sum: 
            return 1
        else:
            return 0
        
    # Check sum
    number = numbers[depth]
    result = 0
    
    result = addsub(numbers, depth + 1, sum + number, target)
    result += addsub(numbers, depth + 1, sum - number, target)
    return result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from queue import Queue

def solution(numbers, target):
    result = 0
    number_queue = Queue()
    number_queue.put((0, 0)) # depth, sum
    
    while number_queue.qsize() > 0:
        current = number_queue.get()
        current_depth = current[0]
        current_sum = current[1]
    
        # Check sum
        if current_depth == len(numbers):
            if current_sum == target:
                result += 1
            continue
        
        current_number = numbers[current_depth]
        number_queue.put((current_depth + 1, current_sum + current_number))
        number_queue.put((current_depth + 1, current_sum - current_number))
            
    return result