closest-subsequence-sum

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 an integer array <code>nums</code> and an integer <code>goal</code>.

You want to choose a subsequence of <code>nums</code> such that the sum of its elements is the closest possible to <code>goal</code>. That is, if the sum of the subsequence&#39;s elements is <code>sum</code>, then you want to minimize the absolute difference <code>abs(sum - goal)</code>.

Return the minimum possible value of <code>abs(sum - goal)</code>.

Note that a subsequence of an array is an array formed by removing some elements (possibly all or none) of the original array.

&nbsp;
Example 1:

<pre>
Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6.
This is equal to the goal, so the absolute difference is 0.
</pre>

Example 2:

<pre>
Input: nums = [7,-9,15,-2], goal = -5
Output: 1
Explanation: Choose the subsequence [7,-9,-2], with a sum of -4.
The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.
</pre>

Example 3:

<pre>
Input: nums = [1,2,3], goal = -7
Output: 7
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 40</code></li>
	<li><code>-107 &lt;= nums[i] &lt;= 107</code></li>
	<li><code>-109 &lt;= goal &lt;= 109</code></li>
</ul>

minAbsDifference

Closest Subsequence Sum

Minimize the Difference Between Target and Chosen Elements

minimize-the-difference-between-target-and-chosen-elements

最小化目标值与所选元素的差

Partition Array Into Two Arrays to Minimize Sum Difference

partition-array-into-two-arrays-to-minimize-sum-difference

将数组分成两个数组并最小化数组和的差

Minimum Operations to Form Subsequence With Target Sum

minimum-operations-to-form-subsequence-with-target-sum

使子序列的和等于目标的最少操作次数

Find the Sum of Subsequence Powers

find-the-sum-of-subsequence-powers

求出所有子序列的能量和

Bit Manipulation

Array

Two Pointers

Dynamic Programming

Bitmask

Sorting

给你一个整数数组 <code>nums</code> 和一个目标值 <code>goal</code> 。

你需要从 <code>nums</code> 中选出一个子序列，使子序列元素总和最接近 <code>goal</code> 。也就是说，如果子序列元素和为 <code>sum</code> ，你需要 最小化绝对差 <code>abs(sum - goal)</code> 。

返回 <code>abs(sum - goal)</code> 可能的 最小值 。

注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。

 

示例 1：

<pre>输入：nums = [5,-7,3,5], goal = 6
输出：0
解释：选择整个数组作为选出的子序列，元素和为 6 。
子序列和与目标值相等，所以绝对差为 0 。
</pre>

示例 2：

<pre>输入：nums = [7,-9,15,-2], goal = -5
输出：1
解释：选出子序列 [7,-9,-2] ，元素和为 -4 。
绝对差为 abs(-4 - (-5)) = abs(1) = 1 ，是可能的最小值。
</pre>

示例 3：

<pre>输入：nums = [1,2,3], goal = -7
输出：7
</pre>

 

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 40</code></li>
	<li><code>-107 &lt;= nums[i] &lt;= 107</code></li>
	<li><code>-109 &lt;= goal &lt;= 109</code></li>
</ul>