子集总和：返回所需子集的变体

Question

问题描述：

给出一个整数列表和一个目标和，我们需要返回另一个包含布尔值的列表。此布尔值列表表示我们正在寻找的子集。

示例：

输入：列表（3、34、4、12、5、2），目标= 9。

输出：（false，false，true，false，true，false）（因为4 + 5 = 9；请注意，此解决方案不是唯一的，但是问题仅要求一个任意的解决方案）。

我的尝试：

我首先编写了一种检查解决方案是否存在的方法：

boolean subsetSumRec(List<Integer> list, int i, int sum) { //i is the index of the last element in list
    if(sum==0){
        return true;
    } else if(i<0 || sum<0){
        return false;
    }
    boolean include = subsetSumRec(list,i-1,sum-list.get(n));
    boolean exclude = subsetSumRec(list,i-1,sum);
    return include || exclude;
}

我创建了一个新的ArrayList（类型：布尔型）resultList，将其作为输出。我的计划是更新方法subsetSumRec中的resultList。就像这样：

private boolean subsetSumRec(List<Integer> list, int i, int sum) {
    if(sum==0){
        return true;
    } else if(list.size()<=0 || sum<0){
        return false;
    }
    res.add(true);
    boolean include = subsetSumRec(list,i-1,sum-list.get(i));
    boolean exclude;
    if(include == false){
        res.remove(true);
        res.add(false);
        exclude = subsetSumRec(list, i - 1, sum);
    }
    return include || exclude;
}

这没有提供所需的结果，但是我看不到出了什么问题。如何进行优化？

如果未在subsetSumRec中更新resultList，那么我将不得不放弃检查是否存在解决方案并使用回溯算法的方法（无需动态编程！）。我不知道如何从最后一个开始。有人可以给我提示如何解决此问题的回溯算法（伪代码吗？）。

提前感谢。

Answer 1

这是JavaScript中递归的一个示例。如果可行，我们返回第二个列表，否则返回false。

function f(A, S, B=new Array(A.length).fill(false), i=A.length - 1){
  if (A[i] == S){
    B[i] = true
    return B
  }
    
  if (i == 0){
    if (A[i] == S){
      B[i] = true
      return B
    }
    return false
  }
  
  if (A[i] <= S){
    let maybeB = f(A, S - A[i], B, i - 1)
    if (maybeB){
      B[i] = true
      return B
    }
  }

  return f(A, S, B, i - 1)
}

var A = [3, 34, 4, 12, 5, 2]

console.log(JSON.stringify(A))
console.log(JSON.stringify(f(A, 9)))