同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2060_子集和问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 46| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504287827800-Problem List-采集的数据-后羿采集器.html

Pro.ID

2060

Title

子集和问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2060

AC

Submit

130

Ratio

6.15%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

子集和问题的一个实例为 ( S, c )。其中，S={ x₁ ，x₂ ，…，x_n }是一个正整数的集合，c是一个正整数。对于给定的正整数的集合S，是否存在S的一个子集S1，使得。

试设计一个解子集和问题的回溯法。

输入

输入第一行有两个正整数n 和c，n 表示S的大小（ 0 < n < 7000 ），c是子集和的目标值。接下来的一行，有n个正整数，表示集合S中的元素。

输出

Description

试设计一个解子集和问题的回溯法。

Input

输入第一行有两个正整数n 和c，n 表示S的大小（ 0 < n < 7000 ），c是子集和的目标值。接下来的一行，有n个正整数，表示集合S中的元素。

Output

本题有多解，请输出满足条件的、按升序排列最小的子集。

如：存在两个解：2 2 6 和 6 4，则输出2 2 6这个解。当问题无解时，输出 "No Solution!"

Sample Input

5 10
2 2 6 5 4

Sample Output

2 2 6

Author

John

样例输入