2026-02-14：含上限元素的子序列和。用go语言，给你一个长度为 n 的整数数组 nums 和一个正整数 k。对于每个整数 x（1 ≤ x ≤ n），先把

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)
}

# -*-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()

#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;

    return0;
}