子集和问题：返回所需子集的变体

Question

问题描述：

给定一个整数列表和一个目标总和，我们需要 return 另一个包含布尔值的列表。这个布尔列表代表我们正在寻找的子集。

示例：

输入：列表（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 中的一个递归示例。如果解决方案可行，我们return第二个列表，否则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]
var S = 9

console.log(JSON.stringify(A))
console.log(`Target: ${S}`)
console.log(JSON.stringify(f(A, S)))

S = 199
console.log(`\nTarget: ${S}`)
console.log(JSON.stringify(f(A, S)))

子集和问题：返回所需子集的变体

Subset Sum Problem: Returning a Variant of the Required Subset

java

algorithm

backtracking

subset-sum