java - 子集和问题: Returning a Variant of the Required Subset

Question

问题描述:

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

示例:

输入:列表 (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(类型: boolean 值)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]
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)))