부분수열의 합 C++ - 백준 1182

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

백트래킹으로 수열을 하나 하나 만들고 길이가 $N$이면

종료하는 solve함수를 사용해 해결했다.

탐색할 때 범위를 자기 인덱스 + 1을 해주어 겹치는 경우의 수를 제거했다.

코드는 다음과 같다.

#include <iostream>
using namespace std;

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

void solve(int l, int sum, int ni){
	if(sum==s && l!=0) cnt++;
	if(l==n) return;
	
	for(int i=ni;i<n;i++){
		solve(l+1,sum+arr[i],i+1);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> s;
	for(int i=0;i<n;i++){
		cin >> arr[i];
	}
	solve(0,0,0);
	cout << cnt;
}