[BaekJoon 1182번 / JAVA] 부분수열의 합

Question

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

---

💡 Solution

아래는 예제 입력으로 주어진 수열입니다.

-7 -3 -2 5 8

 

위 예시에서 부분 수열의 합이 0이 되는 경우는 {-3, -2, 5}으로 한 가지입니다.

 

우선 정답을 찾기 위해 첫 번째 인덱스인 -7부터 탐색합니다. 예를 들어, {-7, -3, -2}와 {-3, -2}라는 부분 수열이 있다고 생각해봅시다. 둘의 차이점은 보시다시피 -7이 포함되어 있냐, 없냐의 차이입니다. 

 

즉, 아래와 같은 상황에서 탐색을 이어날 것입니다.

현재 인덱스의 값을 포함하지 않을 경우라면, solve(탐색할 값의 인덱스, 현재 포함되어 있는 부분 수열의 합);

현재 인덱스의 값을 포함할 경우라면, solve(탐색할 값의 인덱스, 현재 포함되어 있는 부분 수열의 합 + 현재 인덱스의 값)

 

여기서 탐색할 값의 인덱스란 다음 재귀 때 넘겨줄 인덱스를 말합니다. 즉 다음 인덱스를 넘겨주어야 하므로 "현재 인덱스 + 1"이 될 것입니다.

 

이런 식으로 탐색하는 인덱스 값이 포함되어 있냐, 없냐의 두 상황에서 재귀를 통해 정답을 구하시면 됩니다.

solve 함수로 넘겨주는 2번째 인자인 sum이 결국 S와 같다면, 해당 부분 수열이 정답 중 한 가지의 경우가 되므로 count값을 증가시켜주면 됩니다.

 

💻 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ1182 {
	static int N, S;
	static int[] arr;
	static int count;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		arr = new int[N];
		count = 0;
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		solve(0, 0);
		if (S == 0) {  //S가 0이면 공집합도 될 수 있으므로 1개를 뺴준다.
			System.out.println(count - 1);
		}
		else {
			System.out.println(count);
		}

	}
	
	public static void solve(int index, int sum) {
		if (index == N) {
			if (sum == S) {
				count++;
			}
			return;
		}
			
		solve(index + 1, sum + arr[index]); //현재 인덱스의 값 더하기
		solve(index + 1, sum);  //현재 인덱스의 값 넘어가기
	}

}