关于递归求解问题求教.寻找递归大神！

Question

【问题描述】
　　已知一个一维数组A1..N，又已知一整数M。 如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。（要求用递归函数编写程序）
【输入样例】
　　5
　　1 2 3 4 5
　　12
【输出样例】
　　YES

我的想法是分成两部分，数组中的每一个数都存在选和不选的可能，由此递归。我写了两个递归程序，一个是错的，一个是对的，我不明白错的为什么错了，因为思路和正确的代码是一样的，求大神解答。
--------------------------------------以下是正确的-------------------------------
#include
#include
#include
#include
using namespace std;
int m;
int n,in[100];
int flag=0;
void pd(int in[],int n,int k)
{
if(in[n]==k)
{
flag=1;return ;
}
else if(n==0) return ;
else
{

pd(in,n-1,k);
pd(in,n-1,k-in[n]);
}

}

int main() {

cin>>n;
for(int i=0;i<n;i++)
{
    cin>>in[i];
}
cin>>m;
pd(in,n-1,m);
if(flag)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
return 0;

}
--------------------------------------以下是错误的-------------------------------
#include
#include
#include
#include
using namespace std;
int m;
int n,in[100];
int flag=0;
void pd(int in[],int n,int k,int sum)
{
if(sum==k)
{
flag=1;return ;
}
else if(n==0) return ;
else
{

pd(in,n-1,k,sum);
pd(in,n-1,k,sum+in[n]);
}

}

int main() {

cin>>n;
for(int i=0;i<n;i++)
{
    cin>>in[i];
}
cin>>m;
pd(in,n-1,m,0);
if(flag)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
return 0;

}
---------------------------------------------以上是代码--------------------------
求大神解答，我还想知道这个递归的时间复杂度，不知道该怎么计算，O(n!)，O(2^n)?

Answer 1

时间复杂度应该是O(2^n)，不过这是最坏情况。
你的程序和正确的那个程序还是由点区别的。
你用sum和输入的m一直传递进去，一直在比较。你用的是加法
正确的那个程序传入的是m，并用减法
主要是核心的这两个递归函数的分析，你的，

 void pd(int in[],int n,int k,int sum)
{
//这个判断有点问题，当sum还小于k，但是n此时为1时，往下执行会执行到pd(in,0,k,sum)和pd(in,0,k,sum+in[1])
//然后这里可以明显看出来sum的递加是加到in[1]，那么in[0]还未判断
//下一步递归，pd(in,0,k,sum+in[1])传进去执行的时候，此时sum=sum+in[1]，但是in[0]呢？永远不会执行sum+in[0],因为这里n=0,你已经退出了。
if(sum==k)
{
flag=1;return ;
}
//所以你这里要改成n==-1，防止往下执行，导致n为负数，从而出现sum+in[-1]就可以了。
else if(n==0) return ;
else
{   
pd(in,n-1,k,sum);
pd(in,n-1,k,sum+in[n]);
}

下面是正确的那个程序：

 void pd(int in[],int n,int k)
{
//他采用的是递减的模式，而且是先判断in[]数组里的元素，所以下面判断用n==0
//当in[0]==k时候，或者n==0,都表示执行结束，退出了。
if(in[n]==k)
{
flag=1;return ;
}
else if(n==0) return ;
else
{
pd(in,n-1,k);
pd(in,n-1,k-in[n]);
}

从时间复杂度上，这个正确的最坏情况是O（2^n-1）有小优化。