프로그래머스 < 삼총사 > JavaScript

📍문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/131705

📍알고리즘 분류

- 백트래킹

 

📍문제 풀이

- 중복된 수가 있을 수 있는 정수 배열이 주어진다. 정수 배열에서 3개의 숫자를 뽑아서 (조합)

합이 0이 되는 경우의 수를 구하라

 

백트래킹을 이용해서 조합을 구현할 수 있다

 

📍코드 (JavaScript)

function solution(number) {
  const chosenNums = []; // 뽑힌 숫자들 (조합)
  const isUsed = []; // 중복을 막기 위해 사용됐는지 확인할 배열
  let answer = 0; // 가짓수

  // 백트래킹
  function recursive(depth, start) {
    if (depth === 3) {
      // depth 3에서 조건 확인
      const sum = chosenNums.reduce((acc, cur) => acc + cur, 0);
      if (sum === 0) answer++;
      return;
    }
    // start를 통해 순서대로 탐색될 수 있도록 함
    for (let i = start; i <= number.length; i++) {
      if (!isUsed[i]) {
        chosenNums.push(number[i - 1]);
        isUsed[i] = true;
        recursive(depth + 1, i + 1); // depth = 3 이면 조건 확인하고 return해서 아래 내용 실행 X
        chosenNums.pop();
        isUsed[i] = false;
      }
    }
  }
  recursive(0, 1);
  return answer;
}

console.log(solution([-3, -2, -1, 0, 1, 2, 3])); // 5