[프로그래머스-JS] 삼총사 - 재귀함수

문제

숫자 배열을 입력 받아 배열의 요소인 숫자 3개를 더해서 0이 되는 방법의 수를 return하세요

제한사항

• 3 ≤ number의 길이 ≤ 13
• -1,000 ≤ number의 각 원소 ≤ 1,000
• 서로 다른 학생의 정수 번호가 같을 수 있습니다.

입출력 예

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

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

output = solution([-1, 1, -1, 1]);
console.log(output); //0

3중 for문 풀이

가장 먼저 쉽게 생각 나는 것은 3중 for문이었다.

function solution(number) {
    let answer = 0;
    for(let i = 0; i < number.length; i++){
        for(let j = i+1; j < number.length; j++){
            for(let k = j + 1; k < number.length; k++){
                if(number[i] + number[j] + number[k] === 0){
                    answer++;
                }
            }
        }
    }
    return answer;
}

하지만 시간 복잡도를 줄이기 위해 재귀함수 풀이를 생각해봤는데, 잘 떠오르지 않았다. 😢 아직도 재귀함수 사용법이 익숙하지 않은 것 같다.
다른 사람들의 풀이를 보고 이해하려고 했는데도 쉽지 않았다.

재귀함수 풀이

1. reduce 메서드로 합쳐서 0이 되는 조합을 찾으면 result 에 1을 더해준다.
2. 배열의 요소를 한개씩 추가하면서 재귀함수를 돌리는데, 배열의 길이가 3이 되면 합쳐서 0이 되는 지 검사한다.
   0이 되던, 안되던 (3개만 모이면 if문에 걸려서) return 하여 해당 조합의 턴을 끝내고 for문으로 다른 조합을 찾아낸다.
3. combination( ) 재귀함수를 돌릴 때 두 번째 인자로 i + 1을 넘겨서 같은 수의 조합이 중복되지 않도록 한다.

function solution(number) {
    let result = 0;

    const combination = (current, start) => {
        if (current.length === 3) {
            result += current.reduce((acc, cur) => acc + cur, 0) === 0 ? 1 : 0;
            return;
        }

        for (let i = start; i < number.length; i++) {
            combination([...current, number[i]], i + 1);
        }
    }
    combination([], 0);
    return result;
}

for문 재귀함수로도 3중 for문처럼
첫 번째 두 번째 고정시켜놓고 세 번째 숫자를 쭉 돌고,
끝나면 두 번째 숫자 옮겨서 다시 고정시켜놓고 세 번째 숫자 쭉 돌고,
두 번째 숫자도 옮기는 거 끝나면 첫 번째 숫자 한 칸 이동해서 다시 반복하는 방법이 가능하다는 것을 알게 됐다.