백준 s2 1182 부분수열의 합 c++

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

 

풀이

1. 1+3+2나 1+2+3이나 동일하므로, 중복되지 않도록 하였다.

2. S=3 일 때, 1+2로 S 조건을 충족해도 1+2+(-2)+(-1) 이나 0을 더하는 등 조건을 만족하는 부분수열이 더 있을 수도 있기 때문에 return으로 끝내지 않고 더 가야 한다

3. S=0 일 때, func(0)에서 맨 처음 시작이 0이기 때문에 최종 answer에서 -1 해줘야 한다.

 

수도 코드

func (int i) { //i번째 인덱스부터 시작
	if (sum == S)
    	answer++;
    
    for(j: i+1 ~ N-1)
    	sum += arr[j]
        func(j+1)
        sum -= arr[j]
}

 

 

코드

/*boj s2 1182 부분수열의 합*/
#include <iostream>
#define MAXN 22
using namespace std;

int N, S;
int sum = 0;
int answer = 0;
int arr[MAXN];

void func(int i) { // i번째 인덱스부터 시작
    if (sum == S) {
        answer++;
    }

    for (int j = i; j < N; j++) {
        sum += arr[j];
        func(j + 1);
        sum -= arr[j];
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> S;

    for (int i = 0; i < N; i++)
        cin >> arr[i];

    func(0);

    if (S == 0) // 아무 것도 없는 경우 제외
        cout << answer - 1 << "\n";
    else
        cout << answer << "\n";
}