子集合问题算法

来源：百度知道 编辑：UC知道 时间：2024/07/06 19:09:38
这个问题就是给定一个整数集合和一个整数

要求找出是否有这样一个子集合，其中所有元素的和等于给定的整数

该问题是一个NP难问题，不过貌似可以用回溯法求出结果

求算法设计的思路，欢迎大家讨论

在线等

用减法来解决这个问题。

假设给定整数为x.

0 等于x的整数自然就是符合要求的子集。
1 在集合中找出小于x的子集；
2 在子集中逐个取数，剩余的数组成一个新的子集，从x中减掉得到一个新的数x；
3 重复0，1，2步骤。
4 对于符合0的子集就是所需要的子集。

可以用递归的方法生成函数，并用数组存储集合。