「アルゴリズム」と同じサブセット-DFS(深度優先ナビゲーション)

質問する

N個の要素からなる自然数の集合が与えられた場合、その集合を2つの部分集合に分割した場合、2つの部分集合の要素の和が同じである場合は、「YES」を書き、そうでない場合は「NO」を書くプログラム。

2つの部分に分かれている集合こそ集合であり、2つの部分の集合を加算する場合は、入力された元の集合でなければなりません。

例えば、{1,3,5,6,7,10}を入力すると、{1,3,5,7}={6,10}の2つの部分の集合の和が16に等しい場合があることを示す。

▼▼入力説明
第1行は自然数N(1<=N<=10)を与える.
2行目には、集合の要素N個が与えられる.各要素は繰り返しません.サイズは1000000を超えません.
▼▼出力説明
1行目に「YES」または「NO」を出力します.
▼▼入力例1
6
1 3 5 6 7 10
▼▼出力例1
YES

に答える

function solution(arr){
  let answer = "NO";
  let total = arr.reduce((memo,item)=>memo+item,0);
  function DFS(n,sum){
    if(n === arr.length){
        if(total-sum === sum){
          answer = "YES";
          return;
        }
        return;
    }
    DFS(n+1,sum);
    DFS(n+1,sum+array[n]);
  }
  DFS(0,0);
  return answer;
}

▼▼問題の出所

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard