백준 1182번: 부분수열의 합

코드: https://github.com/kgh128/Problem-Solving/blob/main/src/Baekjoon/p1182.java

1. 부분수열의 합을 구하는 함수 구현

재귀함수를 이용하여 부분수열의 합을 구한다. 현재 수열의 수를 sum에 더하고, sum이 목표 값이 S와 같다면 부분수열을 하나 찾았다는 의미로 count 값을 1 증가시킨다. 수열에는 음수도 있으므로 이후에 수가 추가되어 생기는 새로운 부분수열의 합도 S가 될 수 있다. 따라서 이때는 count 값만 증가시키고 return은 하지 않아 다음 부분수열도 검토할 수 있도록 한다.

만약 수열의 인덱스를 의미하는 current 값이 N-1과 같다면 수열의 끝까지 온 것이므로, 더이상 추가될 숫자는 없다. 따라서 이 경우에는 return을 해서 이전 호출로 돌아간다. 그러면 이전 호출의 for문으로 돌아가므로(다음 문단 참고), for문이 돌아 이전 원소 말고 다음 원소를 추가한 부분수열에 대한 합을 구한다.

아직 current 값이 N-1보다 작다면 더 추가할 수 있는 숫자가 남았다는 의미이므로, for문을 돌면서 순차적으로 현재 원소의 다음 원소 ~ 마지막 원소를 부분수열에 추가하면서 해당 부분수열의 합을 구한다.

public static void sumOfSubset(int sum, int current) {
	sum += nums[current];

    if (sum == S) {
		count++;
   	}
    if (current == N-1) {
		return;
	}

	for (int i = current+1; i < N; i++) {
		sumOfSubset(sum, i);
	}
}

부분수열의 합이 S와 같으면 count++를 하고, 바로 return해서 틀렸다. 예를 들어, 수열이 "-3 3 -3 3 -3"이고, S가 -3이라고 하자. 그럼 합이 -3이 되는 부분수열은 "-3", "-3 3 -3", "-3 3 -3 3 -3"으로 총 3개이다. 하지만 틀린 코드로 돌리면 "-3" 상태에서 더이상 다음 원소를 넣어보지 않고 바로 return하므로 답이 1이 나온다. 이런 경우를 방지하기 위하여 sum이 S와 같아져도 return 하지 않았다.

2. 부분수열의 합 구하기

sumOfSubset 함수를 이용하여 부분수열의 합을 구한다. main 함수에서도 for문을 돌면서 순차적으로 수열의 첫번째 원소 ~ 마지막 원소를 부분수열의 첫번째 원소로 주고 sumOfSubset 함수를 호출하였다.

예를 들어, i가 0일 때는 수열의 0번째 원소로 시작하는 모든 부분수열의 합을 구하고, i가 1일 때는 수열의 1번째 원소로 시작하는 모든 부분수열의 합을 구하는 방식이다.

for (int i = 0; i < N; i++) {
	sumOfSubset(0, i);
}