[BOJ] 백준 1182번 : 부분수열의 합 C++ : 아주정은

문제 링크 : https://www.acmicpc.net/problem/1182 <- 여기

오랜만에 문제를 풀어보았다.

부분 수열의 합인데, 완전탐색으로 할수있다. 하지만 겹치는건 카운팅하면 안된다.

그래서 들어갔던건 빼고 그 뒤에꺼부터 DFS에 넣어주면 된다.

코드를 확인하면 된다.

#include <iostream>

using namespace std;

int arr[20];
int n, s;
int cnt = 0;

void init_arr(int input) {
	for (int i = 0; i < input; i++) {
		arr[i] = 0;
	}
}

void dfs(int sum, int input) {
	
	if (sum == s and input !=0) {
		cnt++;
	}

	if (input == n) return;

	for (int i = input; i < n; i++) {
		dfs(sum + arr[i], i + 1);
	}
}

int main(void) {
	cin >> n >> s;
	init_arr(n);
	

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	dfs(0, 0);
	cout << cnt << endl;
}