[GDSC Week3-2] 백준 1182번:: 부분수열의 합 (C++)

* 생각한 아이디어 및 문제 풀이

수 하나를 더할 때 마다 답이 아니면 처음부터 진행하는 것이 아닌, 그 수를 빼고 다른 수를 더해 확인하는 백트래킹 방식을 사용하여 재귀함수 형식으로 문제를 풀이한다.
주의할 점은 sum이 해당하는 값에 도달하더라도 뒤의 것을 계속해서 탐색해야한다는 것이다.

 

* 코드

#include <iostream>
using namespace std;

int arr[21];
int N, S, cnt=0;

void backTracking(int start, int sum) {
	if (start >= N) return;
	int tmp = sum;
	tmp += arr[start];
	if (tmp == S) cnt++;
	for (int i=start+1; i<N; i++){
		backTracking(i, tmp);
	}
}

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(NULL);
    
	int tmp;
	cin >> N >> S; 
	for (int i=0; i<N; i++){
	    cin >> arr[i];
	}
	
	for (int i=0; i<N; i++) {
		tmp = 0;
		backTracking(i, tmp);
	}
    cout << cnt;
}

 

* 회고

 

 

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

1182번: 부분수열의 합

https://velog.io/@ynoolee/BackTracking%EB%B0%B1%EC%A4%801182%EB%B2%88

BackTracking_백준1182번