Question

子集和问题

用pascal的搜索与回溯做，要不超时的！急急急
子集和问题
Description
子集和问题的一个实例为〈S,t〉。其中，S={x1,x2,...,xn}是一个正整数的集合，c
是一个正整数。子集和问题判定是否存在S的一个子集S1，使得x∈S1,∑x=c.
试设计一个解子集和问题的回溯法。
«编程任务：
对于给定的正整数的集合S={x1,x2,...,xn}和正整数c，编程计算S 的一个子集
S1，使得x∈S1,∑x=c.
Input
由文件input.txt 提供输入数据。文件第1 行有2 个正整数n 和c，n 表示S 的大小，c
是子集和的目标值。接下来的1 行中，有n 个正整数，表示集合S 中的元素。
Output
程序运行结束时，将子集和问题的解输出到文件output.txt中。
当问题无解时，输出“No Solution!”。
Sample Input
5 10
2 2 6 5 4
Sample Output
2 2 6

Answer 1

用回溯法解这道题，我本来想修改排列树使之可以求出一个集合的所有子集。但是分析了一下，时间复杂度比求全排列并没有多少减少。所以就直接求出全排列来解除此题。(想通了，求子集应该用子集树来解决)
注：这个题用子集树解更简单，时间复杂度更低。类似于0-1背包的回溯法。