[アルゴリズムプール]ターゲット番号

問題の説明

 n個の非負の整数.この数字を適当に加算または減算してターゲット番号を作成したいです.たとえば、[1,1,1,1,1,1]で数値3を作成するには、次の5つの方法があります.

 使用可能な数値の配列番号、ターゲット番号のターゲットをパラメータとして指定したときに、適切に数値を加算して減算して、ターゲット番号を作成する方法の数を返します.

せいげんじょうけん

で与えられた数字は20個未満です.

各数字

は50より大きい自然数である.

目標は自然数が1000より大きいことです.

I/O例

に答える

import copy

def search(numbers, index, target, answer):
    number_arr = copy.deepcopy(numbers)
    if index > len(number_arr)-2 :
        if sum(number_arr[:-1]) + number_arr[-1] == target:
            answer[0] += 1
        
        if sum(number_arr[:-1]) - number_arr[-1] == target:
            answer[0] += 1
        
        return
        
    else:
        search(number_arr, index + 1, target, answer)
        
        number_arr[index] *= -1
        search(number_arr, index + 1, target, answer)
        

def solution(numbers, target):
    answer = [0]
    search(numbers, 0, target, answer)

    return answer[0]

  search(numbers, index, target, answer)は、numbersおよびindexが入力され、search(numbers, index + 1, target, answer)が関数内で再帰的に呼び出され、インデックスのnumbers要素に−1を乗じたときにnumberの和がtargetと一致するかどうかを検証する関数である.
 再帰呼び出し時には、数値[i]に-1を乗じ、パラメータを乗じないで2回呼び出すことで、DFSを使用してバイナリツリーをブラウズする仕組みがあります.最終確認(sum(numbers)==target)はindex == len(numbers)-2で終了して実行され、もう一度深さを下げる必要はなく、最終レベルまでに値を算出して結果を確認することで実行時間を短縮する.
 結果値をresponse[0]に保存し、pythonがintタイプを使用する場合、call by valueのため、再帰呼び出しごとに正しい答えの個数が独立して蓄積されます.これはホットな問題です.したがって、listに保存して、すべての再帰呼び出しの結果値が1つの変数に同期するようにします.

githubアドレス

https://github.com/bjih1999/algorithm/blob/master/programmers/DFS_BFS/%ED%83%80%EA%B2%9F%20%EB%84%98%EB%B2%84/solution.py