프로그래머스 - 소수 만들기

N과 M을 다 풀어보기에는 같은 문제를 여러번 푸는 느낌이라, 프로그래머스의 백트래킹 문제를 풀어보려고 했다. 그런데 프로그래머스를 들어가니 레벨측정을 위해 문제 하나를 풀어보라는 메세지가 떴다. 그래서 한 번 풀어보았는데 우연찮게도 이 문제를 백트래킹을 사용하여 풀게 되었다.

풀이
주어진 숫자들 중 3개씩 뽑는 모든 경우를 실행해 보아야 한다. 따라서 백트래킹 알고리즘을 사용하기로 했다.
1. 첫번째 숫자를 뽑고 , 두번째 숫자를 뽑고, 세번째 숫자를 뽑는다. (뽑은 숫자는 int[] primeN에 저장한다)
2. 각 N번째 숫자를 뽑을 때 항상 nums배열의 0번째 index부터 마지막 index까지 탐색하며 뽑아보는데, 이 때 뽑은 숫자가 이전 단계들에서 뽑았던 숫자면 (i <= before) 해당 숫자는 skip한다
3. 숫자 3개를 뽑으면(selectedN == 3) 소수인지 검증한다.

class Solution {
    static int[] primeN = new int[3];
    static int answer = 0;
    static int[] nums;
    public int solution(int[] nums) {
        this.nums = nums;
        go(0, -1);
        return answer;
    }
    static void go(int selectedN, int before){
        // 3개 고르면
        if(selectedN == 3){
            //다 더해서 소수면 answer++
            int sum = 0;
            for(int i = 0; i < 3; i++){
                sum += primeN[i];
            }
            //소수인지 검증하는 로직
            //자기의 약수가 1이랑 자신 말고 없으면
            boolean isPrime = true;
            for(int i = 2; i < sum/2; i++){
                if(sum % i == 0){
                    isPrime = false;
                    break;
                }
            }
            if(isPrime){
                answer++;
            }
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(i <= before){
                continue;
            }
            primeN[selectedN] = nums[i];
            go(selectedN+1, i);
        }
    }
}

다른 풀이들을 검색해 보았더니 다들 딱히 백트래킹 알고리즘을 사용하진 않고 그냥 구현으로 풀었다. 하지만 어떻게 풀든 별 차이는 없는 것 같다.