文章目录一、问题介绍二、动态规划求解思路三、Java代码实现一、问题介绍子集和问题(SubsetSumProblems,SSP),它是复杂性理论中最重要的问题之一。SSP会给定一组整数a1,a2,....,ana_1,a_2,....,a_na1,a2,....,an,最多nnn个整数,我们需要判断是否存在一个非空子集,使得子集的总和为MMM整数?如果存在则需要输出该子集。例如,集合给定为[5,2,1,3,9][5,2,1,3,9][5,2,1,3,9],子集之和为999;答案是肯定的,因为子集[5,3,1][5,3,1][5,3,1]的总和等于999。这是一个NPNPNP完全问题。是背