C语言回溯法

解题思路:回溯法

注意事项:

参考代码:

#include<stdio.h>
int sum,n;
int a[10];
void dfs(int x,int y)//x、y表示第y个加数是x
{
    a[y]=x;
    if(sum==n)
    {
        printf("%d=",n);
        for(int i=1;i<y;i++)
        {
            printf("%d+",a[i]);
        }
        printf("%d\n",a[y]);
    }
    
    else 
    {
        for(int i=a[y];i<n;i++)
        {
            if(sum+i<=n)
            {
                sum+=i;
                dfs(i,y+1);
                sum-=i;
            }   
        }
    }
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
	    sum+=i;
	    dfs(i,1);
	    sum-=i;
	}
	return 0;
}