Length of the Longest Subsequence That Sums to Target

Medium

Intuit

1 view

Topics:

Dynamic Programming

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.

Example 1:

Input: nums = [1,2,3,4,5], target = 9
Output: 3
Explanation: There are 3 subsequences with a sum equal to 9: [4,5], [1,3,5], and [2,3,4]. The longest subsequences are [1,3,5], and [2,3,4]. Hence, the answer is 3.

Example 2:

Input: nums = [4,1,3,2,1,5], target = 7
Output: 4
Explanation: There are 5 subsequences with a sum equal to 7: [4,3], [4,1,2], [4,2,1], [1,1,5], and [1,3,2,1]. The longest subsequence is [1,3,2,1]. Hence, the answer is 4.

Example 3:

Input: nums = [1,1,5,4,5], target = 3
Output: -1
Explanation: It can be shown that nums has no subsequence that sums up to 3.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
1 <= target <= 1000

Length of the Longest Subsequence That Sums to Target

Medium

Intuit

1 view

Topics:

Dynamic Programming

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.

Example 1:

Input: nums = [1,2,3,4,5], target = 9
Output: 3
Explanation: There are 3 subsequences with a sum equal to 9: [4,5], [1,3,5], and [2,3,4]. The longest subsequences are [1,3,5], and [2,3,4]. Hence, the answer is 3.

Example 2:

Input: nums = [4,1,3,2,1,5], target = 7
Output: 4
Explanation: There are 5 subsequences with a sum equal to 7: [4,3], [4,1,2], [4,2,1], [1,1,5], and [1,3,2,1]. The longest subsequence is [1,3,2,1]. Hence, the answer is 4.

Example 3:

Input: nums = [1,1,5,4,5], target = 3
Output: -1
Explanation: It can be shown that nums has no subsequence that sums up to 3.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
1 <= target <= 1000

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array contain negative numbers, zeros, or just positive integers?
What is the expected return value if no subsequence sums to the target? Should I return 0, null, or throw an exception?
Are duplicate numbers allowed in the input array, and if so, should I consider them distinct elements when forming the subsequence?
What are the constraints on the size of the input array and the target value?
Is the order of elements in the subsequence important? Do I need to maintain the same order as the original array?

Brute Force Solution

Approach

The brute force method for finding the longest subsequence with a target sum is like trying every possible combination. We'll check absolutely every subsequence to see if it adds up to the target, and if it does, we'll compare its length to the longest one we've found so far.

Here's how the algorithm would work step-by-step:

Start by considering all possible subsequences within the given numbers. A subsequence is just a selection of numbers from the original set, where the order is maintained but you can skip numbers.
For each subsequence, calculate the sum of its numbers.
If the sum of the subsequence equals the target sum, we've found a potential candidate.
Check the length of this subsequence. Is it longer than the length of the longest subsequence that sums to the target we've found so far?
If it is longer, remember this subsequence and its length. This is our new best candidate.
Continue this process for every single possible subsequence. Exhaust every option.
After examining all possible subsequences, the one we remembered as the longest is the answer.

Code Implementation

def longest_subsequence_with_target_sum_brute_force(numbers, target):
    longest_subsequence = []

    # Iterate through all possible subsequences
    for i in range(1 << len(numbers)):
        current_subsequence = []
        current_sum = 0

        for j in range(len(numbers)):
            # Check if the j-th element is included in the current subsequence
            if (i >> j) & 1:
                current_subsequence.append(numbers[j])
                current_sum += numbers[j]

        # Check if the current subsequence sums to the target
        if current_sum == target:
            # Check if current subsequence is longer than the longest found so far
            if len(current_subsequence) > len(longest_subsequence):
                longest_subsequence = current_subsequence

    return longest_subsequence

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm iterates through all possible subsequences of the input array. For an array of size n, there are 2^n possible subsequences because each element can either be included or excluded from a subsequence. For each subsequence, we calculate the sum, which takes O(n) in the worst case where the subsequence includes all elements. Although the sum calculation contributes a factor of n, the dominant term is still the generation and consideration of all 2^n subsequences. Therefore, the overall time complexity is O(2^n).

Space Complexity

O(1) – The brute force approach, as described, iterates through all possible subsequences. It calculates the sum and length of each subsequence but doesn't explicitly store all subsequences in memory. It only keeps track of the longest subsequence found so far and its length. Thus, the space required is constant, regardless of the input size N (the number of elements in the input list), as only a few variables are used to store the current sum, current subsequence length, the longest subsequence length, and possibly the subsequence itself. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The key is to efficiently reuse calculations to avoid redundant work. We use a technique to store and recall the results of smaller subproblems to build towards the final answer, making the process much faster.

Here's how the algorithm would work step-by-step:

Consider each number from the input sequence one by one.
For each number, determine if including it can help form a subsequence that sums to the target.
Build a table to store the minimum length required to achieve a particular sum using the numbers considered so far.
If a sum can be achieved by including the current number, update the table with the new length.
If a sum can be achieved without including the current number, keep the existing length.
Choose the minimum length between including and not including the current number to populate the table.
The final entry in the table will give you the length of the longest subsequence that sums to the target.

Code Implementation

def find_longest_subsequence(numbers, target_sum):
    number_count = len(numbers)
    # Initialize a table to store minimum lengths for each sum.
    minimum_lengths = [[float('inf')] * (target_sum + 1) for _ in range(number_count + 1)]
    
    minimum_lengths[0][0] = 0

    for i in range(1, number_count + 1):
        for current_sum in range(target_sum + 1):
            # Determine whether to include the current number or not.
            if numbers[i-1] <= current_sum:

                minimum_lengths[i][current_sum] = min(
                    minimum_lengths[i-1][current_sum],
                    minimum_lengths[i-1][current_sum - numbers[i-1]] + 1
                )

            # If current number exceeds sum, exclude it.
            else:
                minimum_lengths[i][current_sum] = minimum_lengths[i-1][current_sum]

    if minimum_lengths[number_count][target_sum] == float('inf'):
        return -1
    
    # The result holds the length of longest subsequence for target
    return minimum_lengths[number_count][target_sum]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*target) – The algorithm iterates through each of the n numbers in the input sequence. For each number, it potentially updates a table representing sums from 0 up to the target value. Therefore, for each of the n numbers, the algorithm performs computations related to each possible sum up to the target. This results in a time complexity proportional to n multiplied by the target value, leading to O(n*target).

Space Complexity

O(target) – The algorithm utilizes a table to store the minimum length required to achieve a particular sum using the numbers considered so far. This table has a size directly related to the target value. Therefore, the auxiliary space required is proportional to the target sum, resulting in a space complexity of O(target).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, indicating no subsequence sums to the target.
Array with only one element, which equals target	Return 1 as the length of the subsequence is 1.
Array with only one element, which does not equal target	Return 0, indicating no valid subsequence.
Array contains only positive numbers and target is negative	Return 0, as a subsequence of positive numbers cannot sum to a negative target.
Array contains zeros and the target is zero	The subsequence consisting of all zeros is a valid solution, return the count of zeros.
Array contains negative numbers and the target is positive	Standard dynamic programming or recursion with memoization handles this correctly.
Very large array and target, potential integer overflow in sums	Use a data type that can accommodate larger sums, such as long, or check for potential overflow before calculations.
No subsequence sums to the target	Return 0, indicating no valid subsequence exists.