[BOJ] 백준 1182 부분수열의 합

문제링크 : https://www.acmicpc.net/problem/1182

 이 문제는 조건을 만족시키는 부분집합의 개수를 구하는 것이다.
물론 다음과 같은 경우는 같은 부분집합이다.
{1,2}와 {2,1} == 1+2 and 2+1 = 3?
이 경우 두 집합이 다르다고 간주하여 답을 2개로 적으면 안된다. 같은 집합이기 때문이다.

따라서 우리는 기준을 정해야 한다.

나는, 입력받을 때 다른 것들보다 먼저 입력받은 인덱스를 먼저 계산하는 방식을 택했다.
다시말해 1을 체크했다면 2부터 시작할 때에는 1을 거들떠 보지도 않겠다는 뜻이다. 왜냐하면 2부터 시작할때는 1을 거쳤을 것이고 {1, 2}가 계산되었다는 뜻 이기 때문이다.

소스코드 :

#include 
#include 
using namespace std;


int cnt = 0;
int dest;
vector origin;



int Sum(vector v) {
 int t = 0;
 bool flag = false;
 for (int i = 0; i < v.size(); i++) {
  t += v[i];
  flag = true;
 }
 t = flag == true ? t : dest-1;
 return t;
}

void Func(vector v, int s) {
 if (s > origin.size()) {
  return;
 }


 if (Sum(v) == dest) {
  cnt++;
 }

 for (int i = s; i < origin.size(); i++) {
  v.push_back(origin[i]);
  Func(v, i + 1);
  v.pop_back();
 }




}


int main() {

 int n, s;
 
 cin >> n >> s;
 dest = s;
 for (int i = 0; i < n; i++) {
  int a;
  cin >> a;
  origin.push_back(a);
 }
 vector tmp;
 Func(tmp, 0);
 cout << cnt << endl;


}