[Lv 2]目標番号

プログラマ

https://programmers.co.kr/learn/courses/30/lessons/43165

この問題はDFSアルゴリズムで解決できるが,DFSで再帰関数を記述することに慣れていないため,他の人の解プログラマ目標番号を見て理解した.

問題を理解する

n個の要素を持つnumbers要素を追加または減算してtargetを作成できる場合は、数を返す必要があります.各要素は+または-であるため、合計2^nの数値を作成できます.

DFS

ここで利用できる方法は,再帰関数を用いたDFS(深さ優先探索)アルゴリズムである.
1つのノードをブラウズした後、子ノードがなくなると、隣接する親ノードの兄弟ノードにアクセスします.子ノードは兄弟ノードでも参照され、子ノードがない場合は隣接する親ノードの兄弟ノードにアクセスします.

に答える

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

例

次に、solution([1,1,1,1,1],3)を実行する例を示す.

🔍 最後のサブノードを確認

dfs関数の呼び出しに伴い、callスタックをチェックすると、生成されたdfs関数が順次スタックされ、最後のindex=5、sum=5であれば条件(index===numbers.length)に対応し、答え++となり、関数が返され、callスタックからポップアップされる.

🔍 親兄弟ノードの最後のサブノードを確認

dfs(5,5)が返された後、callスタックにスタックされた最後の関数dfs(4,4)に対してdfs(4+1,4−1)が実行される.dfs(5,3)はすべての条件文を満たすので++と答えて返す.
👉 ここで、dfs(4,4)は、dfs(5,5)の親兄弟ノードに相当する.

🔍 すべてのノードのすべてのサブノードをチェック

各ノードの最後の+、最後の-が確認された場合、答えが返されます.