length-of-the-longest-subsequence-that-sums-to-target

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

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

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.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

Example 3:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= target &lt;= 1000</code></li>
</ul>

lengthOfLongestSubsequence

Length of the Longest Subsequence That Sums to Target

Coin Change

coin-change

零钱兑换

Coin Change II

coin-change-ii

零钱兑换 II

Find the Maximum Length of Valid Subsequence I

find-the-maximum-length-of-valid-subsequence-i

找出有效子序列的最大长度 I

Find the Maximum Length of Valid Subsequence II

find-the-maximum-length-of-valid-subsequence-ii

找出有效子序列的最大长度 II

Array

Dynamic Programming

给你一个下标从 0&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>target</code>&nbsp;。

返回和为 <code>target</code>&nbsp;的 <code>nums</code>&nbsp;子序列中，子序列&nbsp;长度的最大值&nbsp;。如果不存在和为 <code>target</code>&nbsp;的子序列，返回 <code>-1</code>&nbsp;。

子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。

&nbsp;

示例 1：

<pre>
输入：nums = [1,2,3,4,5], target = 9
输出：3
解释：总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。
</pre>

示例 2：

<pre>
输入：nums = [4,1,3,2,1,5], target = 7
输出：4
解释：总共有 5 个子序列的和为 7 ：[4,3] ，[4,1,2] ，[4,2,1] ，[1,1,5] 和 [1,3,2,1] 。最长子序列为 [1,3,2,1] 。所以答案为 4 。
</pre>

示例 3：

<pre>
输入：nums = [1,1,5,4,5], target = 3
输出：-1
解释：无法得到和为 3 的子序列。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= target &lt;= 1000</code></li>
</ul>