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

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

✓ Brute Force (Generate All Subsequences)

⏱️ Time: O(2ⁿ × n) Space: O(n)

Use bit manipulation or recursion to generate all 2^n possible subsequences. For each subsequence, check if its sum equals the target and track the maximum length found.

Dynamic Programming (1D)

⏱️ Time: O(n × target) Space: O(target)

Create a DP array where dp[i] represents the maximum length of subsequence that sums to i. For each number, update the DP array by considering including that number in existing subsequences.

Memoization (Top-Down DP)

⏱️ Time: O(n × target) Space: O(n × target)

Recursively try including or excluding each element, using memoization to cache results for (index, current_sum) pairs. This avoids recomputing the same subproblems.

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

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

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

✓ Linear 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

Length of the Longest Subsequence That Sums to Target - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Generate All Subsequences) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler