알고리즘 with python.05

 

더하거나 빼거나

1번째 코드

경우의 수의 결과값을 반환한다.

numbers = [2, 3, 1]       #[2, 3, 1] 라고 하면 쉽게 해결이 되는지 고민
target_number = 0
result = []


def get_all_ways_to_by_doing_plus_or_minus(array, current_index, current_sum, all_ways):
    if current_index == len(numbers):
        all_ways.append(current_sum)
        return
    get_all_ways_to_by_doing_plus_or_minus(
        array, current_index + 1, current_sum + numbers[current_index], all_ways
    )
    get_all_ways_to_by_doing_plus_or_minus(
        array, current_index + 1, current_sum - numbers[current_index], all_ways
    )
    
    
print(get_all_ways_to_by_doing_plus_or_minus(numbers, 0 , 0, result))
print(result)
    

결과값 None [6, 4, 0, -2, 2, 0, -4, -6]

 

우리가 해결하고자 하는 문제는 target_number가 몇개 있는지 알고싶은 것이다.

때문에 코드의 수정이 필요하다.

 

2번째 코드 완성

numbers = [2, 3, 1]
target_number = 0
result_count = 0


def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
    if current_index == len(numbers):
        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 + numbers[current_index])
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
                                                       current_sum - numbers[current_index])


print(get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0))
print(result_count)
    

번외

3번째 코드 완성

numbers = [1, 1, 1, 1, 1]
target_number = 3
result_count = 0


def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
    if current_index == len(numbers):
        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 + numbers[current_index])
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
                                                       current_sum - numbers[current_index])


print(get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0))
print(result_count)