题目

任何一个大于1的自然数，总可以拆分成若干个小于n的自然数之和。
如当n=7，总共有14种拆法
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4

代码

#include <iostream>
using namespace std;
int a[1001];
int total=0;
int n;
void print(int k){
    total++;
    cout<<n<<"=";
    for(int i=1;i<k;i++){
        cout<<a[i]<<'+';
    }
    cout<<a[k]<<endl;
}
void search(int k,int s){
    for(int i=a[k-1];i<=s;i++){
        if(i<n){
            a[k]=i;
            s-=a[k];
            if(s==0) print(k);
            else search(k+1,s);
            s+=a[k];
        }
    }
}
int main(){
    cin>>n;
    a[0]=1;
    search(1,n);
    cout<<total;
}

分析

基础套模版题

1 for循环范围

• 要求是每个数大于或等于前面那个数 可以 1+1+1.。。或1+2+2.。。，不可以是2+1+1.
• 对于第K层，所以i应该大于等于a[k-1]
• 也可以全选，从1到n，然后用if语句排除不能选的

2 判断可选

• 其实都可以选
• 运行发现会有一个单独的7
• 所以有一个不能选，就是n本身，加上判断

 if(i<n)

3 选中后

• 1 用a[k]保存结果
• 2 s-=i，减掉i的值
• 3 继续递归搜索

        if(i<n){
            a[k]=i;
            s-=a[k];
        }

4 结束条件

• s为0则打印一个结果，total总数加1

        if(i<n){
            a[k]=i;
            s-=a[k];
            if(s==0) print(k);
            else search(k+1,s);
        }

5 需要回溯

• s的值加回去

s+=a[k];