(递归描述)根据上排给出十个数，在其下排填出对应的十个数

腾讯面试题：

给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数

要求下排每个数都是先前上排那十个数在下排出现的次数。

上排的十个数如下：

【0，1，2，3，4，5，6，7，8，9】

 

举一个例子，

数值: 0,1,2,3,4,5,6,7,8,9

分配: 6,2,1,0,0,0,1,0,0,0

0在下排出现了6次，1在下排出现了2次，

2在下排出现了1次，3在下排出现了0次....

以此类推..

刚才看了下网上搜索到的TOP5的解决方案，有的是纯数学的分析，有的看起来是错误的，其它的则不甚满意。遂自己分析并写出了一个版本。

本代码优势：多个约束条件降低了解空间规模，使用递归描述简化了代码量。

#include <iostream>
#include <algorithm>
using namespace std;

int stats[10];


//添加约束条件，降低解空间规模
void set_stats(int* top)
{
    for(int i=0;i<10;++i)
    {
        if(top[i]>=10 || top[i]<0)//大于10或者小于0的数，出现次数只能为0
        {
            stats[i] = 0;
        }
        else if(top[i]<2)
        {
            stats[i] = 9;
        }
        else
        {
            stats[i] = 10/top[i];//出现top[i]的次数*top[i]<=10
        }
    }
}
/** 
 * @top:上排数组
 * @bottom:下排数组
 * @i:遍历到的数组索引
 * @sum:bottom数组之和为10（约束条件，进一步降低解空间规模）
 */     

bool findTen(int* top, int* bottom, int i, int sum)
{
    if(i<10 && sum>=0)
    {
        for(int j=min(stats[i],sum); j>=0;--j)//尝试遍历多种情况，j的取值从0到stas[i]，考虑到约束条件，故为min(stats[i],sum)
        {
            bottom[i] = j;
            if(findTen(top, bottom, i+1, sum-j))//找到可行数组就退出
                break;
        }
    }
    else if (sum<0)
    {
        return false;
    }
    else
    {
        while(i<10) bottom[i++]=0;//如果i<10时sum就为0，则bottom后面的数必然为0
        // 检查是否满足约束条件
        for(int k1=0;k1<10;++k1)
        {
            int ct = 0;
            for(int k2=0;k2<10;++k2)
            {
                if(top[k1] == bottom[k2])
                {
                    ct++;
                }
            }
            if(ct!=bottom[k1])
            {
                return false;
            }
        }
        //输出
        for(int k1=0;k1<10;++k1)
        {
            cout << bottom[k1] << ' ';
        }
        cout << endl;
        return true;
    }

}

int main()
{
    int top[] = {0,1,2,3,4,5,6,7,8,9};
    int bottom[10];
    set_stats(top);
    findTen(top,bottom,0,10);
    return 0;
}