2026-02-14：含上限元素的子序列和。用go语言，给你一个长度为 n 的整数数组 nums 和一个正整数 k。对于每个整数 x（1 ≤ x ≤ n），先把数组中大于 x 的数都缩小到 x，得到一个新的数组。然后在这个新数组中，是否能够取出一个非空的、保持原来相对顺序的子序列，使其元素之和恰好等于 k？

将对每个 x（按 x=1 到 n 顺序）的可行性用一个长度为 n 的布尔数组 answer 表示，其中 answer[i]（下标从 0 开始）表示当 x = i+1 时是否存在这样的子序列。

1 <= n == nums.length <= 4000。

1 <= nums[i] <= n。

1 <= k <= 4000。

输入： nums = [4,3,2,4], k = 5。

输出： [false,false,true,true]。

解释：

对于 x = 1，限制后的数组为 [1, 1, 1, 1]。可能的和为 1, 2, 3, 4，因此无法选出和为 5 的子序列。

对于 x = 2，限制后的数组为 [2, 2, 2, 2]。可能的和为 2, 4, 6, 8，因此无法选出和为 5 的子序列。

对于 x = 3，限制后的数组为 [3, 3, 2, 3]。可以选择子序列 [2, 3]，其和为 5，能选出满足要求的子序列。

对于 x = 4，限制后的数组为 [4, 3, 2, 4]。可以选择子序列 [3, 2]，其和为 5，能选出满足要求的子序列。

题目来自力扣3685。

算法过程详细描述

1. 问题理解与转化

• 输入：整数数组 nums（长度 n，每个元素 ≤ n）和正整数 k（≤ 4000）
• 对于每个 x（1 ≤ x ≤ n），需要判断是否存在一个非空子序列（保持原顺序），该子序列中所有元素都 ≤ x，并且元素之和等于 k
• 注意：子序列中的元素不是修改原数组，而是从"原数组中大于 x 的元素被限制为 x"的数组中选取

2. 核心算法思想

算法采用增量构造 + 二进制状态压缩动态规划的思想：

• 先对原数组排序（虽然会破坏原顺序，但子序列的顺序约束在这种情况下不影响可行性判断，因为值相同）
• 从小到大枚举 x 值（1 到 n）
• 维护一个二进制数 f，表示当前能够组成的子序列和集合
• f 的第 i 位为 1 表示可以组成和为 i 的子序列

3. 具体执行步骤

步骤1：排序

• 将 nums 数组按升序排序

步骤2：初始化

• n = 数组长度
• ans = 长度为 n 的布尔数组，初始全 false
• f = 二进制数 1（表示初始时可以组成和为 0 的子序列）
• u = 2^(k+1) - 1（掩码，用于将 f 限制在 k 位以内）

步骤3：枚举 x 从 1 到 n

• 对于每个 x，执行以下操作：

  3.1 加入所有值为 x 的元素

  • 从数组已排序位置 i 开始，将所有等于当前 x 的元素加入 DP 状态
  • 每个元素的加入方式：将当前 f 左移该元素的值，与原 f 进行或运算
  • 加入后与掩码 u 进行与运算，保持只关心 ≤ k 的和

  3.2 判断当前 x 是否可行

  • 枚举从"大于 x 的数"中选取 j 个 x（j 从 0 到 min(剩余元素个数, k/x)）
  • 对于每个 j，检查 f 的第 (k - j*x) 位是否为 1
  • 如果存在这样的 j 使得该位为 1，说明可以组成和为 k 的子序列：
    • j 个 x 来自大于 x 的元素（每个被限制为 x）
    • 剩余的 (k - j*x) 由已加入的 ≤ x 的元素组成
  • 若找到可行方案，将 ans[x-1] 设为 true 并停止当前 x 的检查

步骤4：输出结果

• 返回 ans 数组

4. 示例分析（以题目为例）

nums = [4,3,2,4], k = 5

排序后：[2,3,4,4]

• x=1：无等于1的元素，DP状态只能组成和0；剩余元素数=4，最多可取5个1，检查所有j发现无法得到5 → false
• x=2：加入元素2，DP状态可组成0,2；剩余元素数=3，最多可取2个2（k/x=2），检查j=0,1,2：均无法得到5 → false
• x=3：加入元素3，DP状态可组成0,2,3,5；剩余元素数=2，最多可取1个3，j=1时检查(5-3)=2，DP有2 → true
• x=4：加入元素4（第一个4），DP状态可组成0,2,3,4,5,6,7；剩余元素数=1，最多可取1个4，j=1时检查(5-4)=1，DP无1；但j=0时检查5，DP有5（来自3+2）→ true

复杂度分析

时间复杂度

• 排序：O(n log n)
• 主循环：外层循环 n 次，内层：
  • 添加元素：每个元素被处理一次，每次操作 O(1)（位运算）
  • 检查可行性：对于每个 x，最多检查 k/x + 1 个 j，总检查次数 ≈ ∑(k/x) ≈ k * log n
• 总时间复杂度：O(n log n + n * k/x) ≈ O(n log n + k * n)（在 n, k ≤ 4000 时，实际约 1.6×10^7）
• 更精确：O(n log n + n + k * H(n)) ≈ O(n log n + k log n)

额外空间复杂度

• 排序：根据排序算法不同，可能需要 O(log n) 或 O(n) 的栈空间
• DP 状态：只使用常数个 big.Int 变量（f, u, shifted）
• 结果数组：O(n)
• 总额外空间：O(n)（主要来自存储结果数组）

注意：big.Int 内部存储二进制位所需空间为 O(k/wordsize)，k ≤ 4000，所以约 4000 位 ≈ 63 个 64位字，可视为常数空间。

Go完整代码如下：

package main

import (
	"fmt"
	"math/big"
	"slices"
)

func subsequenceSumAfterCapping(nums []int, k int) []bool {
	slices.Sort(nums)

	n := len(nums)
	ans := make([]bool, n)
	f := big.NewInt(1)
	u := new(big.Int).Lsh(big.NewInt(1), uint(k+1))
	u.Sub(u, big.NewInt(1))

	i := 0
	for x := 1; x <= n; x++ {
		// 增量地考虑所有恰好等于 x 的数
		for i < n && nums[i] == x {
			shifted := new(big.Int).Lsh(f, uint(nums[i]))
			f.Or(f, shifted).And(f, u) // And(f, u) 保证 f 的二进制长度 <= k+1
			i++
		}

		// 枚举（从大于 x 的数中）选了 j 个 x
		for j := range min(n-i, k/x) + 1 {
			if f.Bit(k-j*x) > 0 {
				ans[x-1] = true
				break
			}
		}
	}
	return ans
}

func main() {
	nums := []int{4, 3, 2, 4}
	k := 5
	result := subsequenceSumAfterCapping(nums, k)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def subsequence_sum_after_capping(nums, k):
    nums.sort()
    
    n = len(nums)
    ans = [False] * n
    # 使用位掩码，f 的第 b 位为 1 表示存在和为 b 的子序列
    f = 1
    # 只需要保留到 2^(k+1) - 1
    mask = (1 << (k + 1)) - 1
    
    i = 0
    for x in range(1, n + 1):
        # 增量地考虑所有恰好等于 x 的数
        while i < n and nums[i] == x:
            # f = f | (f << nums[i])，并截断到 mask
            f = (f | (f << nums[i])) & mask
            i += 1
        
        # 枚举（从大于 x 的数中）选了 j 个 x
        for j in range(min(n - i, k // x) + 1):
            if f >> (k - j * x) & 1:
                ans[x - 1] = True
                break
    
    return ans


def main():
    nums = [4, 3, 2, 4]
    k = 5
    result = subsequence_sum_after_capping(nums, k)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <vector>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <climits>

std::vector<bool> subsequenceSumAfterCapping(std::vector<int> nums, int k) {
    std::sort(nums.begin(), nums.end());

    int n = nums.size();
    std::vector<bool> ans(n, false);

    // 使用bitset来存储可达和的状态
    // 只需要考虑和不超过k的状态
    std::bitset<100001> f;  // 假设k最大为100000，可以根据需要调整
    f[0] = 1;

    int i = 0;
    for (int x = 1; x <= n; x++) {
        // 增量地考虑所有恰好等于x的数
        while (i < n && nums[i] == x) {
            f = f | (f << nums[i]);
            i++;
        }

        // 枚举（从大于x的数中）选了j个x
        int max_j = std::min(n - i, k / x);
        for (int j = 0; j <= max_j; j++) {
            if (k - j * x >= 0 && f.test(k - j * x)) {
                ans[x - 1] = true;
                break;
            }
        }
    }

    return ans;
}

int main() {
    std::vector<int> nums = {4, 3, 2, 4};
    int k = 5;
    std::vector<bool> result = subsequenceSumAfterCapping(nums, k);

    // 打印结果
    std::cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        std::cout << (result[i] ? "true" : "false");
        if (i < result.size() - 1) {
            std::cout << ", ";
        }
    }
    std::cout << "]" << std::endl;

    return 0;
}