알고리즘 :: 백준 :: Bruteforce :: 1182 :: 부분수열의 합

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

문제접근

• 시간제한은 2초이고 정수의 개수 N은 1부터 20까지로 적은 범위가 주어졌음을 눈치챈다.
• 간단히 a, b, c 3개의 숫자를 이용해서 만들 수 있는 덧셈 조합을 생각해보면 다음과 같다.
  • a, b, c, a+b, a+c, b+c, a+b+c
  • 나올 수 있는 조합의 개수는 $2^n - 1$개이므로 이 문제에 bruteforce를 적용할 경우 시간복잡도는 $O(2^n)$이다.
  • 상한값 $2^{20} - 1$ 은 1,048,575이므로 시간제한 내에 충분히 풀 수 있음을 눈치챈다.
• 위 사고과정을 거쳐서 우리는 이 문제에 bruteforce를 적용하고자 한다.
• 재귀를 사용해서, i번째 인덱스의 요소를 더하는 경우와 더하지 않는 경우로 나눠서 전역탐색 하고자 한다.

코드

#include <iostream>
using namespace std;

static constexpr int MAX = 20;
static int N, S, result;
static int arr[MAX];

void solve(int idx, int sum){
	sum += arr[idx]; //우선 해당 숫자를 더한다
	if (idx >= N) return;		// [기저1] - 범위 초과시 return
	if (sum == S) result++;		// [기저2] - S를 찾은 경우 경우의 수 추가
	solve(idx + 1, sum - arr[idx]); // idx번 요소를 더하지 않는 경우
	solve(idx + 1, sum); 		// idx번 요소를 더하는 경우
}
int main() {
	cin >> N >> S;
	for (int i = 0; i < N; i++) cin >> arr[i];
	solve(0, 0);
	cout << result << endl;
}

결과