set-theory - 对于从 1 到 n 的所有数字存在唯一子集的集合的数量，使得子集的元素之和等于该数字

Question

给定一个数字 n，我们必须找到集合的数量，使得从 1 到 n 的每个数字都可以通过添加该集合的一些元素来唯一地形成，并且该集合的数字之和必须等于 n。例如，如果 n=5，则 {1,1,1,1,1}, {1,2,2}, {1,1,3} 有效，{1,1,1,2} 无效，因为 3 = 1 + 1 + 1 和 3 = 1 + 2 即 3 不是唯一形成的。{1,2,4} 也是无效的，因为即使从 1 到 4 的所有数字都是唯一形成的，它的元素总和不是 7 5. 这是 CodeChef (Money Matters)的问题表。我已经看到了一些答案，但仍然无法解决。有人可以给我一些提示或方向吗？
n 范围：n<10^9

Answer 1

想象一个 N × N 矩阵，其中每个元素最多为 N。用 2 个循环构建这个矩阵。然后每一行总和为 N 是一个解决方案。

当 N = 5 构建时：

0 0 0 0 0
0 0 0 0 1
0 0 0 0 2
0 0 0 0 3
0 0 0 0 4
0 0 0 0 5 SOLUTION
0 0 0 1 1
0 0 0 1 2
0 0 0 1 3
0 0 0 1 4 SOLUTION 
0 0 1 0 1 
etc.

Answer 2

一些递归可能会有所帮助：

function GetSets(int TotalToHit)
{
   solutions += {TotalToHit};
   for int i = 1; i <= TotalToHit / 2; i ++
   {
     solutions += { i, GetSets(TotalToHit - i) };
   }

   return solutions;
}