我会更好地为初学者解释标题。我的问题与常见的问题非常相似：查找整数数组的所有排列问题。
在给定一个整数列表和一个目标数字的情况下，我试图找到是否可以从列表中选择任何数字组合，以便它们的和与目标匹配。它必须使用函数式编程实践来完成，所以这意味着所有的循环和突变都被取消了，只是聪明的递归。充分披露：这是一项家庭作业，方法标题由教授按原样设置。这就是我所拥有的：
public static Integer sum(final List<Integer> values) {
if(values.isEmpty() || values == null) {
return 0;
}
else {
return values.get(0) + sum(values.subList(1, values.size()));
}
}
public static boolean groupExists(final List<Integer> numbers, final int target) {
if(numbers == null || numbers.isEmpty()) {
return false;
}
if(numbers.contains(target)) {
return true;
}
if(sum(numbers) == target) {
return true;
}
else {
groupExists(numbers.subList(1, numbers.size()), target);
return false;
}
}
sum方法经过测试并且有效，groupExists方法就是我正在研究的方法。我认为它非常接近，如果给定一个列表[1，2，4]，它将为3和10等目标返回true，但为6返回false，这让我很困惑，因为1，2，3的顺序是正确的，并加到6。很明显，缺少了一些东西。此外，我看到的主要问题是，它没有测试所有可能的组合，例如，第一个和最后一个数字没有作为一种可能性相加。
更新：根据Simon的回答工作了一段时间后，我看到的是：
public static boolean groupExists(final List<Integer> numbers, final int target) {
if(numbers == null || numbers.isEmpty()) {
return false;
}
if(numbers.isEmpty()) {
return false;
}
if(numbers.contains(target)) {
return true;
}
if(sum(numbers.subList(1, numbers.size())) == (target - numbers.get(0))) {
return true; }
else {
return groupExists(numbers.subList(1, numbers.size()), target);
}
}
为了方便起见，请声明
static Integer head(final List<Integer> is) {
return is == null || is.isEmpty()? null : is.get(0);
}
static List<Integer> tail(final List<Integer> is) {
return is.size() < 2? null : is.subList(1, is.size());
}
那么你的功能是：
static boolean groupExists(final List<Integer> is, final int target) {
return target == 0 || target > 0 && head(is) != null &&
(groupExists(tail(is), target) || groupExists(tail(is), target-head(is)));
}
实际上，对基本情况加上最后一行进行定期检查并不奇怪，在这一行中，左操作数和右操作数分别搜索包含或不包含头的"组"。
我写它的方式让人一眼就能清楚地看到，这些都是纯函数，但由于这是Java而不是FP语言，所以这种写它的方法非常不理想。最好将任何多次发生的函数调用缓存到最终的本地变量中。当然，这仍然是照本宣科的。
假设您有n数字a[0]，a[1]。。。，a[n-1]，并且您想要找出某个子集是否与N求和。
假设你有这样一个子集。现在，要么包含a[0]，要么不包含。如果它被包括在内，那么必须存在a[1]的子集。。。，CCD_ 8和CCD_。如果不是，则存在a[1]的子集。。。，CCD_ 11和CCD_。
这将引导您找到一个递归解决方案。
检查所有组合都是阶乘(您的实现中缺少一点)。为什么不尝试一种不同的(动态)方法：请参阅《编程竞赛搭车指南》，第1页(子集总和)。
你的主要方法是：
boolean canSum(numbers, target) {
return computeVector(numbers)[target]
}
CCD_ 13返回具有可与CCD_ 14的集合求和的所有数字的向量。方法computeVector递归执行起来有点棘手，但您可以执行以下操作：
boolean[] computeVector(numbers, vector) {
if numbers is empty:
return vector
addNumber(numbers[0], vector)
return computeVector(tail(numbers), vector);
}
addNumber将取向量并用新的"可行"数字"填充"(请参阅搭便车者了解解释)。addNumber也可能有点棘手，我把它留给你。基本上，你需要以创造性的方式编写以下循环：
for(j=M; j>=a[i]; j--)
m[j] |= m[j-a[i]];
通过在每次递归中询问一个非常简单的决定，可以获得所有可能组合的列表。这个组合包含我列表的标题吗？要么有，要么没有，所以每个阶段有2条路径。如果任何一条路径都能找到解决方案，那么我们希望返回true。
boolean combination(targetList, sourceList, target)
{
if ( sourceList.isEmpty() ) {
return sum(targetList) == target;
} else {
head = sourceList.pop();
without = combination(targetList, sourceList, target); // without head
targetList.push(head);
with = combination(targetList, sourceList, target); // with head
return with || without;
}
}