[プログラマ]ターゲット番号

5846 ワード
DFS テキストリンク
問題のソース

問題の説明


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個未満です.
    • 各数字
  • は50より大きい自然数である.
  • 目標は自然数が1000より大きいことです.

    • 説明する

  • 再帰DFSを使用した.ちょっとバカみたいで、
    • def dfs(numbers, i, res, ans):
    if i == len(numbers):
        return 1 if res == ans else 0
    return dfs(numbers, i+1, res + numbers[i], ans) + dfs(numbers, i+1, res - numbers[i], ans)

def solution(numbers, target):
    answer = dfs(numbers, 0, 0, target)
    return answer
    基板部分のチェックを開始したときにエラーが発生しました.
    if i == len(numbers) - 1: # 리스트의 길이만큼 돌았을 때 (마지막수 연산 안했는데 바로 결과 체크함 ㅜ)
	return 1 if res == ans else 0
    このまま
    チェック式の答えは、リストの長さ+1で行うべき最後の数または減算結果を報告することができます!

    他人の解答


    私のようにdfs()関数を構築して解く人もたくさんいます.
    因子は4つ使わざるを得ないようです.
    ゲゼ草を持ってきました.
    solution()関数自体をdfs()と書きました.
    引き裂いて...
    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])
    わあ本当に...どうしてそんな考えがあるの?
    もし私もたくさん解けば、こうなります.
    [CodeKata Dart] Sum of positive
    TIL Day-25