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

문제 : 링크텍스트

풀이 point

값을 더하고 안더하고 두 선택을 할 수 있음
visit 배열 없이 값을 더하거나 더하지 않는 두 선택을 구현

풀이 순서

백트래킹으로 구현 가능
undefined

코드

//백준 1182, 부분수열의 합

#include <iostream>
#include <vector>
#include <queue>

int N, S;
int cnt{0};
int arr[30];

void solve(int sum, int k){
    if(k == N){
        if(sum == S) ++cnt;
        return;
    }
    solve(sum, k+1); //안 더했을 떄
    solve(sum+arr[k], k+1); //더했을 떄
}

int main(){
    
    std::cin >> N >> S;
    for(int i{0}; i<N; ++i) std::cin >> arr[i];

    solve(0, 0);
    
    if(S == 0) --cnt;
    std::cout << cnt;
    return 0;
}

2025-01-08T01:45:54.921Z