介绍

子集之和问题是指从一个给定的集合中找到元素的子集，这些元素的总和等于一个给定的数字 K，我们考虑的是这个集合只包含非负值。假设输入的集合是唯一的（没有重复的）。

子集之和的穷举式搜索算法：

寻找和为 K 的子集的一种方法是考虑所有可能的子集。一个幂集包含了从一个给定的集合产生的所有子集。这样一个幂集 (opens new window)的大小是 2^N。集合的幂集（英语：power set），定义为由该集合全部子集为元素构成的集合。

子集之和的回溯算法：

使用穷举搜索，我们考虑所有的子集，不管它们是否满足给定的约束。回溯算法（Backtracking）可以用来对要选择的元素进行系统的考虑。 假设给定的 4 个元素的集合，例如 w[1]...w[4] 。树可以用来设计回溯算法。下面的树描述了生成可变大小元组（tuple）的方法。

当我们沿着树的深度往下走时，我们会添加到目前为止的元素，如果添加的总和满足明确的约束，我们将继续进一步生成子节点。只要不满足约束条件，我们就停止进一步生成该节点的子树，并回溯到前一个节点，探索尚未探索的节点。在许多情况下，它可以节省大量的处理时间。

伪代码：

if(subset is satisfying the constraint)
    print the subset
    exclude the current element and consider next element
else
    generate the nodes of present level along breadth of tree and
    recur for next levels

当我们结合显性和隐性约束（constraints）时，回溯的力量就出现了，当这些检查失败时，我们就停止生成节点。我们可以通过加强约束检查和对数据进行预排序（presorting）来改进上述算法。通过对初始数组进行排序，一旦到目前为止的总和大于目标数，我们就不需要考虑数组的其他部分（如果子树不满足约束条件，它就会修剪子树）。我们可以回溯并检查其他的可能性。

同样地，假设数组被预排序，我们找到了一个子集。只有当下一个节点满足约束条件时，我们才能生成排除当前节点的下一个节点。

实现

JavaScript

/*
 *
 *  Sum of Subset problem
 *
 *  Given an ordered set W of non-negative integers and a value K,
 *  determine all possible subsets from the given set W whose sum
 *  of its elements equals to the given value K.
 *
 *  More info: https://www.geeksforgeeks.org/subset-sum-backtracking-4/
 */

/*
 * @param {number[]} set Original set of numbers
 * @param {number[]} subset Subset being evaluated
 * @param {number} setIndex Index from set of last element in subset
 * @param {number} Sum of elements from subset
 * @param {targetSum} The target sum on which the subset sum is compared to
 * @returns {number[][]} Subsets whose elements add up to targetSum
 */
const sumOfSubset = (set, subset, setindex, sum, targetSum) => {
  // Base case where the subset sum is equal to target sum
  // Evaluation of following subsets on this path will always add up to
  // greater than targetSum, so no need to continue
  if (sum === targetSum) return [subset]

  // This and following subsets on this path will always add up to
  // greater than targetSum, so no need to continue
  if (sum > targetSum) return []

  // Initialize results array. Will contain only valid subsets
  let results = []

  // Slice gets from the set all the elements at the right of the last element
  // to be evaluated (last element of subset)
  // forEach iterated on the resulting array
  set.slice(setindex).forEach((num, index) => {
    // The next subset to be evaluated, current subset plus next element
    const nextSubset = [...subset, num]

    // Next index from the set. Current set index plus iteration index
    // index starts at 0, so a + 1 is required
    const nextSetIndex = setindex + index + 1

    // Sum of elements from the next subset to be evaluated
    const nextSum = sum + num

    // Call recursively the sumOfSubset for the nextSubset
    const subsetResult = sumOfSubset(
      set,
      nextSubset,
      nextSetIndex,
      nextSum,
      targetSum
    )

    // Concat the recursive result with current result array
    results = [...results, ...subsetResult]
  })

  // Return results
  return results
}

参考

• Subset Sum | Backtracking-4 - GeeksforGeeks (opens new window)