数组子集和求解的O(n√n)同元素分组优化算法工作原理是什么

前提说明 #

我们要解决的问题为：给定总和为n的正整数数组，输出所有可以通过数组子集凑出的和值。常规01背包解法的时间复杂度为O(n²)，在n较大时性能不足，而同值分组优化可以将复杂度降到O(n√n)。 #

核心前提：不同元素的数量为O(√n) #

这个特性是优化的基础，推导逻辑非常简单：

• 所有小于等于√n的不同正整数最多有√n个
• 所有大于√n的元素，每个最多在数组中出现1次（出现2次的话仅这两个元素的和就超过n），因此最多有n/(√n+1) ≈ √n个不同值
  两者相加，数组中不同元素的总数量最多为O(√n)。

算法工作原理 #

这个优化本质是把01背包转化为多重背包问题，再通过多重背包的优化手段降低复杂度，具体步骤如下：

1. 预处理分组：遍历原数组，统计每个数值v出现的次数cnt，将相同数值的元素归为一组，最终得到k=O(√n)个分组。
2. 动态规划定义：用一维布尔数组dp[x]表示是否可以凑出和为x，初始状态dp[0] = true（空集和为0）。
3. 按组更新dp数组：对每个分组(v, cnt)，我们需要实现「可以选择1~cnt个v加入已有的和值」的更新逻辑，常用的两种实现方案如下：

方案1：二进制拆分法 #

将cnt个相同数值v拆分为log2(cnt)个新的虚拟物品，拆分规则为把cnt分解为2的幂次之和：
比如cnt=5可以拆分为1,4，1和4可以组合出1~5之间的任意整数，对应选1个到5个v的情况。
拆分完成后把每个虚拟物品当成普通01背包物品处理，即执行dp[x] = dp[x] | dp[x - k*v]（k为拆分出来的系数）。
每个分组的处理复杂度为O(n log cnt)，总复杂度为O(n * Σ log cnt) = O(n√n)。

方案2：剩余计数优化法 #

额外维护一个辅助数组rem[x]，表示凑出和x时最多还能使用多少个当前分组的v：

• 从小到大遍历和值x从v到n
  • 如果dp[x]已经为true，说明不需要用当前分组的v凑x，设置rem[x] = cnt
  • 如果dp[x-v]为true且rem[x-v] > 0，设置dp[x] = true，rem[x] = rem[x-v] - 1
    这个方案每个分组的处理复杂度为O(n)，总复杂度严格为O(n√n)，实现更简单。

示例 #

假设数组为[1,1,1,2,2,3]，总和n=10，分组后得到(1,3)、(2,2)、(3,1)：

1. 初始dp = [1,0,0,0,0,0,0,0,0,0,0]
2. 处理(1,3)后，dp[0]~dp[3]均为true
3. 处理(2,2)后，dp[0]~dp[7]均为true
4. 处理(3,1)后，dp[0]~dp[10]均为true，即所有0~10的和都可以凑出。

内容的提问来源于stack exchange，提问作者Dachuan Huang