[프로그래머스] 삼총사

문제

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다.

예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다.

또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.

한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.

풀이

배열이 주어지면 모든 조합을 구하여 합이 0이 되는 것을 구하면 된다.
정말 간단히 생각하면 3번의 반복을 하면 된다.
하지만 필자는 for문을 3번까지 가는 것을 좋아하지 않는다.

따라서 백트랙킹을 이용하여 조합을 구현하였다.
참고로 순열은 아니다.
예시의 배열이 주어져 있다면 -2 3 0과 -2 0 3은 같은 것으로 취급해야 되기 때문이다.

class Solution {
    static int answer = 0;
    public int solution(int[] number) {
        boolean[] visited = new boolean[number.length];
        check(number,  visited, 0, number.length, 3, 0);

        return answer;
    }

    static void check(int[] arr, boolean[] visited, int start, int n, int r, int count) {
        if (r == 0) {
            if (count == 0) {
                answer++;
            }
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            check(arr, visited, i + 1, n, r - 1, count + arr[i]);
            visited[i] = false;
        }
    }

    static void print(boolean[] visited, int[] number) {
        for (int i = 0; i < visited.length; i++) {
            if (visited[i]) {
                System.out.print(number[i] + " ");
            }
        }
        System.out.println();
    }
}

https://github.com/Win-9/Algorism/tree/main/programers/%EC%82%BC%EC%B4%9D%EC%82%AC