LeetCode 3685 - Subsequence Sum After Capping Elements

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Dynamic Programming, Sorting

Solution

Here is a complete, rigorous study companion-style solution guide for LeetCode 3685 - Subsequence Sum After Capping Elements, following your requested format and voice.

Problem Understanding

We are given an integer array nums of size n and a positive integer k. For any integer x from 1 to n, we define the capped array capped_x by replacing each element nums[i] with min(nums[i], x). The task is to determine, for each x, whether there exists a subsequence of capped_x whose sum is exactly k. We are to return a boolean array answer where answer[i] corresponds to x = i + 1.

Formally, the input consists of:

nums[0..n-1], with 1 <= nums[i] <= n
k, with 1 <= k <= 4000

The output is:

answer[0..n-1] such that answer[i] is true if there exists a subsequence of capped_(i+1) summing to k, and false otherwise.

Constraints indicate that n can be up to 4000, so any naive solution with complexity O(n * 2^n) is infeasible.

Important observations:

Capping is non-decreasing with respect to x. If a sum is achievable at some x, it remains achievable for all higher x.
Subsequence sum problems are classically solved with dynamic programming.

Edge cases include:

k smaller than the smallest element: must check if subsequence of 1s can reach k.
k larger than the sum of all elements: answer is false for all x.
nums contains repeated maximum values: capping may be needed to avoid exceeding k.

Approaches

Brute Force:

The naive approach iterates over all x = 1..n, generates capped_x, and tries all subsequences using a power set approach. The sum of each subsequence is checked against k. This approach is correct but requires O(n * 2^n) time and O(n) space for generating subsets, which is not feasible for n = 4000.

Optimal Approach:

Key observations enable a better solution:

Monotonicity of Capping: If a sum is achievable for x, it is achievable for any x' > x.
Subsequence Sum via Counting: Since nums[i] <= n and k <= 4000, a frequency-based approach can bound the number of needed sums.
Two-Pointer / Greedy Insight: By sorting nums, for each x we can focus on elements ≤ x and compute the achievable sums using a sliding window or prefix sums.

The optimal approach combines counting and prefix sum tracking, maintaining a boolean array dp[s] indicating whether sum s is achievable. For each x, we only need to add elements ≤ x to dp and propagate sums. Once dp[k] becomes true, all larger x inherit the true result. This reduces the complexity to O(n * k) and space O(k).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * 2^n)	O(n)	Check all subsequences for each x; infeasible for n=4000
Optimal	O(n * k)	O(k)	Use DP on achievable sums and monotonicity of capping

Algorithm Walkthrough

Initialize answer[0..n-1] as false. Initialize dp[0..k] as false with dp[0] = true (sum 0 is always achievable).
Sort nums in non-decreasing order. This allows us to process smaller elements first.
Initialize a pointer i = 0 to traverse nums.
Iterate x = 1..n:

a. Add all nums[j] ≤ x (starting from pointer i) into dp. For each element num, iterate s = k..num downward and set dp[s] |= dp[s - num]. This ensures each sum is only counted once per element.

b. If dp[k] is true, set answer[x-1] = true. Additionally, because of monotonicity, all subsequent answer[y] for y > x-1 are also true and can be filled immediately, then break. 5. Return answer.

Why it works:

The DP array maintains the invariant: dp[s] is true if and only if a subsequence of elements ≤ current x sums to s.
Monotonicity guarantees that once a sum is achievable for x, it remains achievable for all higher x, justifying early termination.

Python Solution

from typing import List

class Solution:
    def subsequenceSumAfterCapping(self, nums: List[int], k: int) -> List[bool]:
        n = len(nums)
        answer = [False] * n
        dp = [False] * (k + 1)
        dp[0] = True

        nums.sort()
        i = 0  # pointer to next element in sorted nums

        for x in range(1, n + 1):
            while i < n and nums[i] <= x:
                num = nums[i]
                for s in range(k, num - 1, -1):
                    dp[s] = dp[s] or dp[s - num]
                i += 1
            if dp[k]:
                for j in range(x - 1, n):
                    answer[j] = True
                break

        return answer

Explanation:

dp[s] tracks achievable sums up to k.
Sorting nums allows sequential inclusion of elements ≤ x.
The inner loop iterates backward to prevent double-counting an element in the same iteration.
Once dp[k] is true, all larger x inherit true, consistent with monotonicity.

Go Solution

func subsequenceSumAfterCapping(nums []int, k int) []bool {
    n := len(nums)
    answer := make([]bool, n)
    dp := make([]bool, k+1)
    dp[0] = true

    sort.Ints(nums)
    i := 0

    for x := 1; x <= n; x++ {
        for i < n && nums[i] <= x {
            num := nums[i]
            for s := k; s >= num; s-- {
                dp[s] = dp[s] || dp[s-num]
            }
            i++
        }
        if dp[k] {
            for j := x - 1; j < n; j++ {
                answer[j] = true
            }
            break
        }
    }

    return answer
}

Go-specific notes:

make([]bool, k+1) initializes the DP array.
sort.Ints(nums) sorts the slice in-place.
Loops and DP propagation are analogous to Python.

Worked Examples

Example 1

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

Sorted nums = [2,3,4,4]
dp = [True, False, False, False, False, False] initially

x	Newly included nums	dp[k]	answer
1	none ≤ 1	False	[False,...]
2	2	dp[2]=True	False
3	3	dp[5]=True	[False, False, True, True]
4	4	already dp[5]=True	True

Example 2

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

Sorted nums = [1,2,3,4,5]
For x=1..3, inclusion of elements ≤ x allows sum 3 via [1,2], [3], etc.
Monotonicity fills answer[0..4] = True.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n*k)	Each element ≤ x is processed once; for each, propagate sums up to k
Space	O(k)	DP array stores achievable sums only

Sorting adds O(n log n) but is dominated by O(n*k).
Monotonicity allows early termination, but worst-case remains O(n*k).

Test Cases

# Provided examples
assert Solution().subsequenceSumAfterCapping([4,3,2,4], 5) == [False,False,True,True]  # Example 1
assert Solution().subsequenceSumAfterCapping([1,2,3,4,5], 3) == [True