淘宝算法见习生的一个笔试题，智商被鄙视了

淘宝算法实习生的一个笔试题，智商被鄙视了…
好像是个经典的问题，有点思路但就是写不好代码。发出来给大家交流交流。
问题：有N个蛋和M个篮子，把蛋放到M个篮子里，每个篮子都不能为空。另外，需要满足：任意一个小于N的正整数，都能由某几个篮子内蛋的数量相加的和得到。写出程序，使得输入一个(N,M)，输出所有可能的分配情况。


------解决方案--------------------
组合数学的内容 运用鸽巢定理可以解决
------解决方案--------------------
昨天好像看见了同样的帖子。。。好像是二进制。。。
------解决方案--------------------
1.先取M个蛋放入M个篮子（一个篮子一个蛋）
2.剩下的（N-M）个蛋按照1，2，4，。。方式依次维持各个篮子中蛋的数量（要有一个篮子保持只有一个蛋），若最后的蛋不是2的方次，有多少放入一个篮子
3.取L(L<=N)个蛋时，应按二进制编码值考虑，如13个蛋：13的二进制码值是1101，则取有8个、4个和1个蛋的篮子即可。
另外：题目不完整，N与M应该有数量关系：M<=N且N<2的M次方
------解决方案--------------------
看来楼主参加了 昨天的笔试。 我觉得条件： 任意一个小于N的正整数，都能由某几个篮子内蛋的数量相加的和得到，已经限制了楼主说的：9个蛋5个篮子，51111、11124、11223、12222都可以的其中的一些选择的可能性
------解决方案--------------------
充分条件：需要编号n的篮子放的鸡蛋数<=前面的鸡蛋数总和+1
n=1时显然满足，然后用归纳法：现在假设前面n个篮子能表示1-Sn（Sn表示前n个篮子鸡蛋总数之和），则第n+1个篮子取1-Sn+1对应能表示1-2Sn+1.总能满足对现有排序方法对应的篮子数M和鸡蛋数N满足上述条件。

必要条件：如果存在需要编号n的篮子放的鸡蛋数>前面的鸡蛋数总和+1，又因为升序，所以前面的鸡蛋数总和+1该数取不到
------解决方案--------------------
期待高人的标准答案
------解决方案--------------------
using System;
using System.Collections.Generic;
using System.Text;

namespace CmpSplitEgg
{
class Program
{
static void Main(string[] args)
{
SplitEgg();
}

public static bool SplitEgg()
{
// 初始化变量，差额diffNum = 鸡蛋数eggNum - 篮子数basketNum
int eggNum = 0, basketNum = 0, diffNum;
// 输入鸡蛋数、篮子数
Input(ref eggNum, ref basketNum);
// 排列结果，并初始化
int[] resultEggs = new int[basketNum];
for(int i=0;i<basketNum;i++)
{
resultEggs[i] = 1;
}

// 差额 = 鸡蛋数 - 篮子数
diffNum = eggNum - basketNum;
if (diffNum < 0)
{
Console.WriteLine("You can't make N < M");
return DoAgain() && SplitEgg();
}
else if (Math.Pow(2, basketNum) <= eggNum)
{
Console.WriteLine("You can't make N > 2^M");
return DoAgain() && SplitEgg();
}

// 对任意一个小于N的数 总能使几个篮子里的鸡蛋总数等于它，则需要编号n的篮子放的鸡蛋数<=前面的鸡蛋数总和+1
// 基于2进制编码是能表示所有数字且位数最小的编码方式，上面条件由此推出
// 假设组合为升序排列，第一个篮子必然为1个鸡蛋
RandomLay(resultEggs, 1, eggNum);

// 是否重新做一次
return DoAgain() && SplitEgg();
}

/// <summary>
/// 重新选择
/// </summary>
public static bool DoAgain()
{
Console.WriteLine();
Console.WriteLine("if you want to enter the N and M again?Yes（Note: if not enter 'Y' or 'y', the application will quit...）");
string choice = Console.ReadLine();
return choice.ToLower() == "y";
}

/// <summary>
/// 输入
/// </summary>
/// <param name="eggNum">鸡蛋数量</param>
/// <param name="basketNum">篮子数量</param>
public static void Input(ref int eggNum, ref int basketNum)
{
while (true)
{
try
{
Console.WriteLine("Please enter the egg number N:");
eggNum = Convert.ToInt32(Console.ReadLine());