[Programmers]DFS/BFS-ターゲット番号(Python)

ソースProgrammers符号化テストハイスコアスイート

DFS/BFS:目標番号[LV 2]

問題の説明

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

-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

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

せいげんじょうけん

与えられた数字は20を超えない.

各数字は1または50未満の自然数です.

TargetNumberは1または1000以下の自然数である.

I/O例

numberstargetreturn[1, 1, 1, 1, 1]35

I/O例説明

問題の例は次のとおりです.
 

Solution

説明する

def DFS(numbers, target, tot):
    if len(numbers) == 0:
        if tot == target:
            return 1
        else:
            return 0
    else:
        res = 0
        res += DFS(numbers[:-1], target, tot + numbers[-1])
        res += DFS(numbers[:-1], target, tot - numbers[-1])
        return res


def solution(numbers, target):
    answer = DFS(numbers, target, 0)

    return answer

これは典型的なDFS問題である.
私はnumbersで最後の要素から始め、再帰関数を呼び出すときに値を渡す必要がある可能性があるので、パラメータ付きDFS関数を作成して使用します.
DFS関数が呼び出されるたびに、numbersの要素の1つが失われ、numbersに要素がない場合は最後まで実行され、totとtargetと比較され、同じ場合は1を返し、異なる場合は0を返します.numbersの要素には加算と減算の2つのケースがあるため、DFS関数を呼び出すには2つの方法がある.その後、2回の呼び出しで2つの戻り値が返されます.

結果

Best Code

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

solutionが呼び出されると、numbersに欠落している要素の値に基づいてtargetから減算または加算されます.これは私が説明したコードの中のtotを必要としません.
私のコードの中のnumbersの要素の記号が+の場合、totの記号は+の場合、このコードはtargetから減算されます.したがって、numbersに要素がなく、target0であれば、条件はすべて満たされる.条件が満たされている場合は1を返し、そうでない場合は0を返します.numbersの要素がまだ存在する場合、再帰関数が再び呼び出され、要素値targetのいずれかを減算すると、2つが呼び出され、受信した戻り値が加算され、返されます.