1182_부분수열의 합

예제 입력 1
5 0
-7 -3 -2 5 8

예제 출력 1
1

study part

• 항상 보는 백트래킹으로 문제를 풀이함

    if(arrange_count==input_count)
    {
        return 0;
    }

    if(sum_value+arrange_value[arrange_count]==input_sum)
    {
        output_count+=1;
    }

• 이부분에서는 먼저 기입한 값과 동일하면 끝 그리고 input_sum이 같으면 output_count+1 형식으로 결과를 도출하고 자함

    check_num(sum_value,arrange_count+1);
    
    check_num(sum_value+arrange_value[arrange_count],arrange_count+1);

    return 0;

• 이부분에서는 진행정도와 값이 계속 누적되는것을 추가하는것으로 합해지는것 이렇게 해서 check_num을 만드는것

code

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int input_count;

int input_sum;

int output_count = 0;

vector <int> arrange_value;

int check_num(int sum_value,int arrange_count)
{
    if(arrange_count==input_count)
    {
        return 0;
    }

    if(sum_value+arrange_value[arrange_count]==input_sum)
    {
        output_count+=1;
    }

    check_num(sum_value,arrange_count+1);
    
    check_num(sum_value+arrange_value[arrange_count],arrange_count+1);

    return 0;
}

int main()
{
    cin>>input_count>>input_sum;
    arrange_value.resize(input_count);

    for(int i = 0 ; i<input_count;i++)
    {
        cin>>arrange_value[i];
    }

    check_num(0,0);

    cout<<output_count;

}