The partial sum problem

描述

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!”.

样例输入

41 2 4 71341 2 4 715

样例输出

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

#include <stdio.h>int e[25];int imt;int num;int dfs(int step,int count)//深度搜索 这里还用到了动态规划的思想 01背包问题{    if(step==num)        return count==imt;    if(dfs(step+1,count))        return 1;    if(dfs(step+1,count+e[step]))        return 1;    return 0;}int main(){    int i,j,k;        while(scanf("%d",&num)!=EOF)    {        for(i=0;i<num;i++)        {            scanf("%d",e+i);        }        scanf("%d",&imt);                if(dfs(0,0))            printf("Of course,I can!\n");        else            printf("Sorry,I can‘t!\n");    }        return 0;}

刚开始写的时候一直超时，很郁闷，搜索了下，发现用深搜加上动态规划的思想便可以解决~，很棒的一种方法~