Length of the Longest Subsequence That Sums to Target

Length of the Longest Subsequence That Sums to Target - Problem

You are given a 0-indexed array of integers nums, and an integer target.

Return the length of the longest subsequence of nums that sums up to target. If no such subsequence exists, return -1.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3], target = 4

› Output: 2

💡 Note: The longest subsequence that sums to 4 is [1,3] with length 2. We can also achieve sum 4 with just [4] if 4 was in the array, but [1,3] gives us the maximum length of 2.

Example 2 — Multiple Solutions

$ Input: nums = [1,1,5,4,5], target = 6

› Output: 3

💡 Note: We can form target 6 with [1,1,4] (length 3) or [1,5] (length 2). The longest subsequence has length 3.

Example 3 — Impossible Target

$ Input: nums = [1,2,3], target = 10

› Output: -1

💡 Note: No subsequence can sum to 10 since the maximum possible sum is 1+2+3=6.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000
1 ≤ target ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers and target sum

Process

Find all subsequences that sum to target

Output

Return length of longest valid subsequence

Key Takeaway

🎯 Key Insight: This is a variant of the unbounded knapsack problem where we maximize the count of items instead of their value.

Asked in

a Amazon 15 G Google 12 M Microsoft 8 f Meta 6

This is a dynamic programming problem similar to the knapsack problem. The key insight is to build up solutions for smaller targets and use them to find the maximum length subsequence. The optimal approach uses 1D DP with time complexity O(n × target) and space O(target).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Generate All Subsequences)	O(2ⁿ × n)	O(n)	Generate all possible subsequences and find the longest one that sums to target
Memoization (Top-Down DP)	O(n × target)	O(n × target)	Use recursion with memoization to explore all possibilities
Dynamic Programming (1D)	O(n × target)	O(target)	Use 1D DP array to track maximum length for each possible sum

Brute Force (Generate All Subsequences) — Algorithm Steps

Generate all 2^n possible subsequences using bit manipulation
For each subsequence, calculate its sum
If sum equals target, update maximum length
Return maximum length found or -1 if none

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 2^n possible subsequences

Check

Calculate sum for each subsequence

Track

Keep maximum length that equals target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int target) {
    int maxLength = -1;
    
    // Generate all 2^n subsequences using bit manipulation
    for (int mask = 0; mask < (1 << numsSize); mask++) {
        int currentSum = 0;
        int currentLength = 0;
        
        // Check each bit in the mask
        for (int i = 0; i < numsSize; i++) {
            if (mask & (1 << i)) {
                currentSum += nums[i];
                currentLength++;
            }
        }
        
        // If this subsequence sums to target, update maxLength
        if (currentSum == target) {
            if (currentLength > maxLength) {
                maxLength = currentLength;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(nums, numsSize, target);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

2^n subsequences to check, each taking O(n) time to sum

✓ Linear Growth

Space Complexity

O(n)

Space for storing current subsequence and recursion stack

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Generate All Subsequences) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler