부분수열의 합

• 사실 백트래킹 보다는 재귀를 통한 완전탐색의 느낌
  --> 다시 돌아와서 새로운 경우를 찾지는 않고 base condition에 도달할 때 까지 쭉 가는 형식이기 때문

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, S, ans=0;
int arr[21];
void func(int idx, int sum){
    /* 모든 요소는 전부 순회해서 돌긴 해야 한다
       --> 이렇게 안하면 S가 0일때 바로 종료된다. */
    if(idx == N){
        if(sum == S){
            ans++;
            return;
        }
    }
    else{
        /* 자신을 포함했거나, 포함안했거나 2가지 경우의수 수행 */
        func(idx+1, sum);
        func(idx+1, sum+arr[idx]);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> S;
    for(int i=0;i<N;i++)
        cin >> arr[i];
    func(0, 0);
    if(S == 0) ans--;
    cout << ans;
    return 0;
}

• 주의할 점
  1) 일단 모든 요소는 순회해야 한다
       --> 그렇지 않으면 S가 0일때 경우 세지도 않고 바로 종료함
  2) isused[] 불필요 !
  isused[]는 다시 돌아와서 사용의 여부에 따라 새로운 경우의 수를 돌게 하기 위해서 사용했음
  하지만, 지금 문제는 그냥 자신을 포함하거나 포함하지 않거나 2가지 경우에 대해 재귀를 돌 뿐 돌아와서 새로운 경우의 수를 찾지는 않기에 isused[]가 필요하지 않다.