Leetcode 2915: Length of the Longest Subsequence That Sums to Target

Problem Link

This problem was featured on LeetCode’s 116th biweekly contest. The problem statement is as follows:

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.

Constraints:

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

If you’ve solved problems like Minimum cost for tickets, Most expensive item that cannot be bought, or Coin change, it’s fairly easy to diagnose this as a dynamic programming problem. But, if not, here is the thought process to come to that conclusion.

1) Take a look at the constraints.

1000 is a relatively small number, so we obviously don’t need a O(n) or even O(nlogn) solution, so we can eliminate possibilities like greedy, etc.

2) Take a look at the parameters.

So you have a list of numbers. The problem will scale by a factor of the length of the numbers which we will call n. But we also have a target. As target increases, we can expect the time/space complexity to increase as well. The time/space complexity we can anticipate to be ~O(n*t) where t is the target.

3) Is the problem easier to solve using a subproblem?

We should be hinting at 2D DP by now simply based on the time and space complexity. But to finalize it, we can ask ourself the classic question: “Can I solve the problem easily if I know the solution to a subproblem?”.

For example, let’s say you are trying to add the number 2 to your solution subsequence and have a target of 3.

Adding 2 obviously adds 2 to your previous sum, so you better have a previous sum of 1 using only the previous elements in num.

This leads us to conclude that Dynamic Programming would appear to be the best approach.

Optimal Substructure

So how can we build up the solution for target using all the numbers in nums? We can break it down into simpler scenarios where we go through every number up to target and limit the number of nums we use.

This way, when we reach the next number in nums at index i we can simply check if we are able to build target - nums[i] using the previous i-1 elements in nums.

So one option for the solution would be:

solution(target, i) = solution(target - nums[i], i - 1) + 1

where i is the index of the element we are trying to add.

But consider another simple scenario. What if we have nums = [1, 2, 3] and target = 3. When we get to nums[i] = 3, we will say:

solution(3, 2) = solution(3 - 3, 2) + 1 = solution(0, 2) + 1

And just logically, we know that to get a target of 0, our length must be 0 and say that the solution is 1. But this is not right since we can also use 1+2 to get a target of 3.

Thankfully, we will have already solved this when nums[i] = 2 by saying that:

solution(3, 1) = solution(3 - 2, 1) + 1 = 1 + 1 = 2

So we have to modify our optimal substructure to also include the option of not using the current number in nums and keeping the same solution from the previous index i-1. In other words:

solution(target, i) = max(solution(target - nums[i], i - 1) + 1, solution(target, i - 1))

One other thing to note is that we will be building our solution bottom-up. This means that we don’t want to encounter nums[i] = 100 before encountering nums[i] = 1. So we have to make sure that we sort nums prior to building our DP table.

Example

With this in mind, let’s run through an explicit example:

nums = [4,1,3,2,1,5], target = 7

After sorting: nums = [1, 1, 2, 3, 4, 5].

Let’s go over 2 explicit cases:

Case 1: target = 4, Using 1, 1, 2

We take the maximum of the previous column (solution(target, i - 1) )and the value at row target - nums[i] column i - 1 or row target = 2 column i = 1 plus 1.

The previous column says we cannot get target = 4 using just 1, 1. The value at the (2, 1) says we can get a sum of 2 using 2 numbers. So we add 1 to this 2 and obtain 3.

Case 2: target = 4, Using 1, 1, 2, 3

We take the maximum of the previous column (solution(target, i - 1) ) and the value at row target - nums[i] column i - 1 or row target = 1 column i = 2 plus 1.

The first option says we can either keep 3 elements or we can get to 4 using 1 + 1 = 2 elements (1+3). This is smaller than the first option, so we will keep the value from the previous column.

Solution

Now, we can finally arrive at the solution. The bulk logic is explained above, but there are some minor tidbits to mention here:

1) We initialize the dp table to be float(-inf) for each column of each row from 0.... target + 1

2) Since the target = 0 can be obtained using 0 elements, we initialize the first row to 0’s

3) When looping through the columns, we don’t want to look at the previous column if we are at the first column. In fact, the only way we can achieve that target t using only a that single number nums[j] is if t == nums[j].

4) When looking back at a previous row in the table, we want to make sure that the row is in bounds (i.e. greater than or equal to 0). Otherwise, Python’s negative indexing could give us bugs.

5) If the previous row is out of bounds, we have no option but to take the value at the previous column

6) The solution will be the maximum value at the last row of the dp table. Note that if we cannot obtain target, we will have float(-inf) in this location, so we take the maximum of that value and -1.

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        nums.sort()
        dp = [[float('-inf')]*len(nums) for i in range(target + 1)]
        dp[0] = [0] * len(nums)
        
        for t in range(1, target + 1):
            for j in range(len(nums)):
                if j == 0:
                    if t == nums[j]:
                        dp[t][j] = 1
                else:
                    if t - nums[j] >= 0:
                        dp[t][j] = max(dp[t][j - 1], dp[t - nums[j]][j - 1] + 1)
                    else:
                        dp[t][j] = dp[t][j - 1]

        return max(dp[-1][-1], -1)
                

I hope this solution helps you make more sense of bottom-up tabulation and 2D dynamic programming!