문제

풀이 방식

문제 설명을 토대로 보았을 때 조합에 관한 문제임을 알 수 있다
자바에서 조합을 구현하고자 할 때 두가지 방법이 있다 - 출처

1. DFS 를 통한 백트래킹 방법

• 해를 찾는 도중 해가 아니게 된다면, 되돌아가서 다시 해를 찾아가는 기법
• 최적화 문제, 결정 문제에 주로 쓰임

// 사용 예시 : 문자열 값, 선택여부 체크 배열 chosen, 시작위치 start, 전체개수 n, 앞으로 선택할 개수 r)
    static void combination_DFS(String arr, boolean[] chosen, int start, int n, int r) {
        if (r == 0) {
            print(arr, chosen, n);
            return;
        }
        if(start == n)
        	return;
    	chosen[start] = true;
        combinationFunc(arr, chosen, start + 1, n, r - 1); // start를 선택한 경우
        chosen[start] = false;
        combinationFunc(arr, chosen, start + 1, n, r); // start를 선택 안한 경우
    }
    // 배열 출력
    static void print(String arr, boolean[] chosen, int n) {
        for (int i = 0; i < n; i++) 
            if (chosen[i]) 
                System.out.print(arr.charAt(i) + " ");            
        System.out.println();
    }

• boolean chosen 을 이용하여 방문한 채로 최대 깊이까지 가게 하고 다시 선택할 개수를 줄이고 방문여부를 false 로 바꾸어 되돌아가면서 해를 찾는다

2. BFS를 통한 재귀

// 사용 예시 : 문자열 값, 선택여부 체크 배열 chosen, 시작위치 start, 전체개수 n, 앞으로 선택할 개수 r)
    static void combinationF_BFS(String arr, boolean[] chosen, int start, int n, int r) {
        if (r == 0) {
            print(arr, chosen, n);
            return;
        }

        for (int i = start; i < n; i++) {
            chosen[i] = true;
            combinationFunc(arr, chosen, i + 1, n, r - 1);
            chosen[i] = false;
        } 
    }	
    // 배열 출력
    static void print(String arr, boolean[] chosen, int n) {
        for (int i = 0; i < n; i++) 
            if (chosen[i]) 
                System.out.print(arr.charAt(i) + " ");            
        System.out.println();
    }

• 이또한 마찬가지로 r 이 0이 될때까지 재귀적으로 해를 찾는다

백트레킹은 함수한번에 두번의 호출이 일어나므로 2의 제곱수 많큼 깊어지면서 함수가 실행이되므로, 재귀방식에 비해 속도가 상대적으로 느리고, 메모리 사용이 적으며,
재귀호출의 경우, 반복문을 통해 함수한번에 N번만큼의 호출이 일어나므로 한 사이클당 N의 제곱수만큼 실행됩니다.
상대적으로 속도가 빠르고, 메모리를 많이 사용합니다.

---

위 두가지 방법중 정석적인 DFS 백트래킹을 통하여 문제에 접근한다

🤔
백트래킹 시작에 앞서 가장 먼저 정의해야할 부분은 해를 찾는 경우를 정의하는것이다
👏 무한 루프에 빠질 수 있으므로 !

인덱스를 이용하여 최대깊이에 도달하였을 때 뒤로 돌아가도록 할 것이기 때문에 이 경우
if (idx == n) 일 경우에 return 시킬 수 있도록한다 (idx 는 현재 인덱스, n 은 배열의 길이)

그리고 만약 최대 깊이까지 도달하였을 때 그 합이 타겟 넘버일 경우 카운트를 1 증가시킨다

---

전체 코드

class Solution {
    static int res = 0;
    static int n;
    public static void dfs(int idx, int sum, int[] numbers, int target){
        // 현재 위치가 마지막 인덱스일 경우
        if(idx == n){
            // 만약 현재 타겟이 여태까지의 합과 같다면 결과 +1
            if(sum==target) res++;
            return;
        }
        dfs(idx+1, sum+numbers[idx], numbers, target);
        dfs(idx+1, sum-numbers[idx], numbers, target);
    }
    
    public int solution(int[] numbers, int target) {
        n = numbers.length;
        dfs(0,0,numbers,target); // 0 번째 인덱스 부터 시작, 합이 0인 채로 시작
        return res;
    }
}