【問題描述】
已知一個一維數組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)?
時間復雜度應該是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）有小優化。
