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

【问题描述】
  已知一个一维数组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)?

查看全部
kingnle
kingnle
2016/11/30 01:35
  • 递归
  • pd
  • string
  • namespace
  • ios
  • 点赞
  • 收藏
  • 回答
    私信
满意答案
查看全部

3个回复