[プログラマ/奥行き、幅優先ナビゲーション(DFS/BFS)/1]ターゲット番号(JS)

1165 ワード
コーディングテスト テキストリンク
出典:プログラマコードテスト深さ、幅優先ナビゲーション(DFS/BFS)第1題
( https://programmers.co.kr/learn/courses/30/lessons/43165 )

問題の説明


n個の非負の整数.この数字を適当に加算または減算してターゲット番号を作成したいです.たとえば、[1,1,1,1,1,1]で数値3を作成するには、次の5つの方法があります.
使用可能な数値の配列番号、ターゲット番号のターゲットをパラメータとして指定したときに、適切に数値を加算して減算して、ターゲット番号を作成する方法の数を返します.

せいげんじょうけん

  • で与えられた数字は20個未満です.
    • 各数字
  • は50より大きい自然数である.
  • 目標は自然数が1000より大きいことです.

    • 解答方法

  • のさらなる四半期と減算された四半期を別々に再コールします.
  • 1に示すように、番号の数で次へ
    計算結果は四半期ごとに保存されます.
  • すべての計算が完了した後、和(sum)がtargetに等しい場合
    数を増やす.
    • は、
  • カウンタを返します.

    • ソースコード

    function solution(numbers, target) {
    let cnt =0
    let sum = 0
    function dfs(row, sum) {
      if (row < numbers.length) {
        dfs(row + 1, sum + numbers[row])
        dfs(row + 1, sum - numbers[row])
      }else{
        if(sum==target) cnt++
      }
    }
    dfs(0, sum)
    return cnt;
}

    ポスト


    実は最近探索と深さ探索の違いを全く知らない.この問題も深さを優先して探索しているが,最終的にはすべてのノードが探索しているが,両者に違いはあるのだろうか.グーグルゲームをしたいのですが
    完走していない選手|Javascript
    【フロントエンドカートンの最適化構想と方案01】webpackは2.2.1からwebpack 4全記録にアップグレードする(現在はwebpack 3.8.1にアップグレードする)