yukicoder-15

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/15 No.15 カタログショッピング] ==

=== Description ===

{{{
#!html
<p>给出$N$个正整数$P_1, P_2, \dots, P_N$。求出所有子集，使得它们的和是$S$。数据保证解不超过$50$个。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$N$ $S$<br>
$P_1$<br>
$P_2$<br>
$\dots$<br>
$P_N$
</p>

<p>$1 \le N \le 31, 1 \le S \le 310000000, 1 \le P_i \le 10000000$。</p>
}}}

=== Output ===

{{{
#!html
<p>输出所有子集，下标从$1$开始。按照字典序从小到大输出。</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
3 220
180
220
280
</pre>
}}}
输出
{{{
#!html
<pre>
2
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
5 150
10
30
40
20
50
</pre>
}}}
输出
{{{
#!html
<pre>
1 2 3 4 5
</pre>
}}}

==== Sample 3 ====
输入
{{{
#!html
<pre>
12 348940
47250
76500
9520
29960
19520
70960
91390
35610
71190
25840
10150
35000
</pre>
}}}
输出
{{{
#!html
<pre>
2 3 4 6 7 8 12
</pre>
}}}

==== Sample 4 ====
输入
{{{
#!html
<pre>
15 445566
13075
16966
20695
21052
25917
25917
28431
31001
44064
47151
59372
63934
63934
66757
88888
</pre>
}}}
输出
{{{
#!html
<pre>
4 5 7 9 10 11 12 14 15
4 5 7 9 10 11 13 14 15
4 6 7 9 10 11 12 14 15
4 6 7 9 10 11 13 14 15
</pre>
}}}

==== Sample 5 ====
输入
{{{
#!html
<pre>
4 20000
10000
10000
10000
10000
</pre>
}}}
输出
{{{
#!html
<pre>
1 2
1 3
1 4
2 3
2 4
3 4
</pre>
}}}

No.15 カタログショッピング

Description

给出$N$个正整数$P_1, P_2, \dots, P_N$。求出所有子集，使得它们的和是$S$。数据保证解不超过$50$个。

Input

$N$ $S$
$P_1$
$P_2$
$\dots$
$P_N$

$1 \le N \le 31, 1 \le S \le 310000000, 1 \le P_i \le 10000000$。

Output

输出所有子集，下标从$1$开始。按照字典序从小到大输出。

Sample

Sample 1

输入

3 220180220280

输出

2

Sample 2

输入

5 1501030402050

输出

1 2 3 4 5

Sample 3

输入

12 34894047250765009520299601952070960913903561071190258401015035000

输出

2 3 4 6 7 8 12

Sample 4

输入

15 445566130751696620695210522591725917284313100144064471515937263934639346675788888

输出

4 5 7 9 10 11 12 14 154 5 7 9 10 11 13 14 154 6 7 9 10 11 12 14 154 6 7 9 10 11 13 14 15

Sample 5

输入

4 2000010000100001000010000

输出

1 21 31 42 32 43 4