• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

꼭 L이 n일때 끝나지 않아도 되지 않나요??

23.02.17 23:02 작성 23.02.17 23:08 수정 조회수 280

0

function solution(arr) {
  let answer = "NO";
  let total = arr.reduce((a, b) => a + b);
  let n = arr.length;

  function DFS(L, sum) {
    if (answer == "YES" || L > n ||sum > total / 2) return;

    if (total / 2 === sum) {
      answer = "YES";
      return;
    } else {
      DFS(L + 1, sum + arr[L]);
      DFS(L + 1, sum);
    }
  }
  DFS(0, 0);
  return answer;
}

어떤 배열의 서로소 부분집합의 합은 같아야 한다

= 서로소인 부분집합의 합은 total의 반이 되면 된다.

라고 한다면 어떤 부분집합의 합이 total의 반이 된다면 바로 끝내면 되지 않을까 해서 여쭤봅니다.

 

if(L===n){
  if((total-sum)===sum){
      answer="YES";
  }
}

 즉 이 부분에서, 꼭 L===n이 되지 않더라도 그 전에 sum이 total의 반이 된다면 끝날 수 있어도 되지 않나요?

 

답변 1

답변을 작성해보세요.

1

안녕하세요^^

네. 그렇게 해도 상관없을 것 같습니다.