백준 1182 부분수열의 합 c++ // 백트래킹

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

1182번: 부분수열의 합

1. 해결과정

함수정의 : (현재깊이, 총합)

탈출조건(기저사례) : 깊이>=n

재귀식 : 현재값(arr[cur])을 더한다 / 안더한다

 

 

2. 전체코드

#include <bits/stdc++.h>
using namespace std;

int n,s,ret;
int arr[24];

//현재깊이, 총합
void go(int cur, int tot) {
	if (cur==n){
		if (tot == s) {
			ret++;
		}
		return;
	}

	//재귀식
	//현재값을 안더하는경우
	go(cur+1, tot);
	//현재값을더하는경우
	go(cur+1,tot+arr[cur]);

}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n>>s;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	go(0,0);
	if (s == 0) ret--;	//공집한인경우 제외하라는 조건있음
	cout << ret;
}