拆分正整数n，求有多少种不同的和式

Question

将正整数n拆分为若干数之和，但是和式中相邻两数的奇偶性必须不相同.例如对于6，6=1+2+3、6=3+2+1、6=1+2+1+2等，但是6=2+4不合法。那么对于n的拆分，共有多少中不同的和式？

输入:3
输出:3
说明:3=1+2、3=2+1、3=3

Answer 1

望采纳！

#include<bits/stdc++.h>
using namespace std;
int t=0,a[40],n,f[31],summ=0,top=0;
void dfs(int index)
{
    if(summ==n)
    {
        t++;
        cout<<n<<"=";
        for(int i=0;i<top;i++)
        {
            if(i!=0)
            cout<<"+";
            cout<<a[i];
        }
        if(t!=4&&a[0]!=n) cout<<";";
        else
        {
         cout<<endl;
         t=0;    
        }
        return ;
    }
    if(summ>n)
    return ;
    for(int i=index;i<=n;i++)
    {
        a[top++]=i;
        summ+=i;
        dfs(i);
        summ-=i;
        top--;
    }
}
int main()
{
  cin>>n;
  dfs(1);
  return 0;
}