(C++) - 백준(BOJ) 1182번 : 부분수열의 합

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

1182번: 부분수열의 합

조합으로 뽑았을 때

부분수열들이 중복될 경우도 고려했었는데 그런걸 고려하는 문제가 아닙니다

 

문제입력 :

4 16

1 7 9 9

output : 2

3번째 9와 2번째 7 뽑는것과 4번째 9와 2번째 7을 뽑는것은 다르다고 보는 것 같습니다. 요거 몰라서 고생했습니다..낄낄

 

마찬가지의 테스트 케이스입니다.

문제입력 :

2 0

0 0

output : 3

(0) , (0) , (0,0) 1번째 0 뽑는경우 2번째 0뽑는경우 1번째와 2번째 뽑는경우 이렇게 3경우가 있습니다.

 

풀이방법

1. 자기 자신은 안뽑는다.

2. 체크안되어있으면 체크 후 해당 노드를 현재 depth에 넣는다.

2. 다음노드에서 탐색을 시작할 때 이전에 체크해두었던 노드를 체크해제한다.

 

Code

#include <iostream>
#include <algorithm>
using namespace std;
int n,s,answer;
int tmp[21], ck[21], num[21];
int dfs(int depth,int index,int m) {
	int sum = 0;
	if (depth == m){
		for (int i = 0; i < m; i++) sum += tmp[i];
		return sum==s;
	}

    int ans = 0;
	for (int i = index; i < n; i++){
		if (!ck[i] ){
			ck[i] = 1;
			tmp [depth]= num[i];
			ans += dfs(depth + 1, i + 1,m);
			ck[i] = 0;
		}
	}
    
    return ans;
}

int main() {
	cin >> n >> s;
	for (int i = 0; i < n; i++) cin >> num[i];
	for(int i = 0; i < n; i++) answer += dfs(0, 0, i + 1);
	cout << answer << '\n';
}​