[백준_1182] 부분 수열의 합 ( dfs - 자바스크립트 )

문제

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

How to Solve ?

 

"양수만 존재하는 부분 집합의 합" 과는 다르게 음수있을 때 투포인터를 사용하면 값이 목표로 하는 "target"과 일치 하지 않을 때

 

1) 앞에서 제거

2) 뒤에서 제거

 

를 모두 해야 하는 경우가 발생한다.

 

즉, 포인터 2개로는 문제를 해결 하지 못하는 경우가 발생 하게 되는데 이는 "DFS"를 통해 해결이 가능하다.

 

 

function dfs(idx, sum) {
  if (idx >= n) {
    return;
  }

  sum += nums[idx];

  if (sum === target) {
    count += 1;
  }
	
  // 더한 값을 없애고
  dfs(idx + 1, sum - nums[idx]);
  // 유지 하고
  dfs(idx + 1, sum);
}

const [n, target] = [5, 0];
const nums = [-7, -3, -2, 5, 8];
let count = 0;
dfs(0, 0);
console.log(count);