[数据结构与算法]题目 1649: 特殊的数字四十

题目

1234是一个非常特殊的四位数，因为它的各位数之和为10，编程求所有这样的四位十进制数。

输入
无

输出
按从小到大的顺序输出满足条件的四位十进制数。每个数字占用一行。

样例输入
无

样例输出
无

解题思路

本题是深度优先搜索符合要求的4位数字，故采用递归的方法，每一次调用递归函数确定一位，当恰好确定完4位，且4位数字之和为10的数字输出即可。

代码

#include<stdio.h>
#include<math.h>
int m;
int min(int a, int b){
    if (a<b)
        return a;
    else
        return b;
}

void find(int n, int sum, int a){
    int i,t,temp;
    if (n==0)
    {
        if (sum==0 && a>=pow(10,m-1))
            printf("%d\n",a);
    }
    else
    {
        if (m==n)
            t = 1;
        else
            t =0;
        for (i=t;i<=min(sum,9);i++)
        {
            temp = a*10+i;
            find(n-1,sum-i,temp);
        }
    }
}

int main()
{
	int sum= 10;
	int n = 4;
	m = n;
	find(n,sum,0);
	return 0;
}