[알고리즘문제] 백준 부분수열의 합

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

1182번: 부분수열의 합

input

 - N : 수열의 갯수

 - S : 부분수열의 합이 되어야 할 값

 - number : 수열

output

 - 부분수열과 S가 일치하는 갯수를 반환.

solution

 - dfs

 - 수열 number와 S, 수열의 index인 idx와 수열의 합으로 next를 넘겨준다.

 - idx를 증가시키며 호출한다.

 - next와 현대 index의 수를 합하며 recursion 호출 한다.

 - 수열의 길이와 index가 같아지면 함수를 return

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int c = 0;
void recursion(vector<int>& number, int S, int idx, int next) {
	if (number.size() == idx) return;
	if (next + number[idx] == S) c++;

	recursion(number, S, idx + 1, next);
	recursion(number, S, idx + 1, next + number[idx]);
}

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

	int N, S, inputNum;
	vector<int> number;
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		cin >> inputNum;
		number.push_back(inputNum);
	}

	recursion(number, S, 0, 0);

	cout << c << "\n";

	return 0;
}

time complexity : O(n²)

space complexity : O(n)