[백준/java] 1182. 부분수열의 합 , 백트래킹

문제 보기

문제

• 입력 : 수열 사이즈 N, 부분수열 목표 합 S, 수열 원소 N개
• 출력 : 합이 S가 되는 크기가 양수인 부분수열의 개수

문제 풀이

부분수열의 공식에 따라, 원소 n개의 수열의 부분수열 갯수는 2^n이다.

매 순간 수를 더할지 더하지 않을지 선택하는 방법으로 모든 부분 수열의 합을 뽑아낼 수 있다. 따라서, 백트래킹 방식으로 부분수열을 탐색할 수 있다.

N = 3이고, 각각의 원소가 1,2,-3인 경우를 살펴보자.

해당 조건일 때, 상태 트리를 그림으로 나타내면 다음과 같다. 원 안의 값은 부분수열의 전체 합을 의미한다. 각 상태는 두 갈래로 분기하고, 왼쪽은 해당 인덱스의 원소를 부분수열에 추가하는 경우이고, 오른쪽은 원소를 부분수열에 추가하지 않는 경우이다. 트리의 리프노드 값들이 부분합 결과이며, 이 중 S의 값과 같은 경우의 수를 구하면 된다.

private static void checkSubsequence(int index,int sum, boolean hasElement) {
        if(index == N) {
            if(hasElement && sum == S) answer++;
            return;
        }
        // 선택할 경우
        checkSubsequence(index + 1, sum + arr[index], true);
        // 선택 안할 경우
        checkSubsequence(index + 1, sum, hasElement);
    }

문제의 조건 중, 크기가 양수인 부분수열 중에서 구하라 했기 때문에 공집합이 아닌 경우에만 고려해야 한다. 따라서, 공집합 여부임을 알 수 있는 hasElement를 추가했다.

시간복잡도

O(2^n) , n<=20 2^20 = 1048576 이므로 적절하다.

🧐백트래킹은 index +1 패턴 호출?

백트래킹 문제를 풀다보니, 재귀 호출 시 인덱스를 index + 1 형태로 호출하는 경우가 많은 거 같다. 이에 대한 이유는, 현재 선택한 원소를 기준으로 다음 원소만을 고려하기 위한 것이고, 이미 선택한 원소를 다시 선택하지 않음으로써 중복을 방지하기 위해 index + 1 을 사용한다. index + 1 패턴은 순서가 없는 조합, 부분집합 생성 시에 매우 유용한 패턴이다.
따라서, 백트래킹에서 자주 사용되는 패턴이다.

🛑 예외 사항
모든 백트래킹 문제에서 인덱스를 +1로 해야 하는 것은 아니다.
순열 문제나 경로 탐색 문제에서는 현재 위치를 제외한 모든 위치를 탐색해야 하므로, index + 1이 아닌 모든 가능한 인덱스를 탐색한다.

느낀점

백트래킹 아직 어렵다..