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} は無効です。 = 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;
}