The partial sum problem

布满荆棘的人生 2022-08-07 15:54 15阅读 0赞

## The partial sum problem ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 2

描述

One day,Tom’s girlfriend give him an array A which contains N integers and asked him:Can you choose some integers from the N integers and the sum of them is equal to K.

输入

There are multiple test cases.  
Each test case contains three lines.The first line is an integer N(1≤N≤20),represents the array contains N integers. The second line contains N integers,the ith integer represents A\[i\](-10^8≤A\[i\]≤10^8).The third line contains an integer K(-10^8≤K≤10^8).

输出

If Tom can choose some integers from the array and their them is K,printf ”Of course,I can!”; other printf ”Sorry,I can’t!”.

样例输入

4
    1 2 4 7
    13
    4
    1 2 4 7
    15

样例输出

Of course,I can!
    Sorry,I can't!

部分和问题！

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    long long a[25],n,sum,sum1;
    int visited[25];
    bool success;
    void dfs(int k)
    {
        int i;
        if(success==true)
        {
            return;
        }
        if(sum1>=sum)
        {
            if(sum1==sum)
            {
                success=true;
                cout<<"Of course,I can!"<<endl;
            }
            return;
        }
        for(i=k;i<=n;i++)
        {
            sum1+=a[i];
            visited[i]=1;
            dfs(i+1);
            sum1-=a[i];
            visited[i]=0;
        }
    }
    int main()
    {
        int i;
        while(cin>>n)
        {
            success=false;
            sum1=0;
            memset(a,0,sizeof(a));
            memset(visited,0,sizeof(visited));
            for(i=1;i<=n;i++)
            {
                cin>>a[i];
            }
            cin>>sum;
            dfs(1);
            if(!success)
            {
                cout<<"Sorry,I can't!"<<endl;
            }
        }
    }