{"id":8095,"date":"2021-02-13T09:08:29","date_gmt":"2021-02-13T17:08:29","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8095"},"modified":"2021-02-13T11:29:21","modified_gmt":"2021-02-13T19:29:21","slug":"leetcode-1755-closest-subsequence-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1755-closest-subsequence-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1755. Closest Subsequence Sum"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1755. Closest Subsequence Sum - \u5237\u9898\u627e\u5de5\u4f5c EP382\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/CiTqABg6oaw?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>You are given an integer array\u00a0<code>nums<\/code>\u00a0and an integer\u00a0<code>goal<\/code>.<\/p>\n\n\n\n<p>You want to choose a subsequence of&nbsp;<code>nums<\/code>&nbsp;such that the sum of its elements is the closest possible to&nbsp;<code>goal<\/code>. That is, if the sum of the subsequence&#8217;s elements is&nbsp;<code>sum<\/code>, then you want to&nbsp;<strong>minimize the absolute difference<\/strong>&nbsp;<code>abs(sum - goal)<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum<\/strong>&nbsp;possible value of<\/em>&nbsp;<code>abs(sum - goal)<\/code>.<\/p>\n\n\n\n<p>Note that a subsequence of an array is an array formed by removing some elements&nbsp;<strong>(possibly all or none)<\/strong>&nbsp;of the original array.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [5,-7,3,5], goal = 6\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> Choose the whole array as a subsequence, with a sum of 6.\nThis is equal to the goal, so the absolute difference is 0.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [7,-9,15,-2], goal = -5\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> Choose the subsequence [7,-9,-2], with a sum of -4.\nThe absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,2,3], goal = -7\n<strong>Output:<\/strong> 7\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums.length &lt;= 40<\/code><\/li><li><code>-10<sup>7<\/sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>7<\/sup><\/code><\/li><li><code>-10<sup>9<\/sup>&nbsp;&lt;= goal &lt;= 10<sup>9<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Binary Search<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/02\/1755-ep382-1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/02\/1755-ep382-1.png\" alt=\"\" class=\"wp-image-8098\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/02\/1755-ep382-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/02\/1755-ep382-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/02\/1755-ep382-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/02\/1755-ep382-2.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/02\/1755-ep382-2.png\" alt=\"\" class=\"wp-image-8099\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/02\/1755-ep382-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/02\/1755-ep382-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/02\/1755-ep382-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>Since n is too large to generate sums for all subsets O(2^n), we have to split the array into half, generate two sum sets. O(2^(n\/2)).<\/p>\n\n\n\n<p>Then the problem can be reduced to find the closet sum by picking one number (sum) each from two different arrays which can be solved in O(mlogm), where m = 2^(n\/2).<\/p>\n\n\n\n<p>So final time complexity is O(n * 2^(n\/2))<br>Space complexity: O(2^(n\/2))<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minAbsDifference(vector<int>& nums, int goal) {\n    const int n = nums.size();\n    int ans = abs(goal);\n    vector<int> t1{0}, t2{0};\n    t1.reserve(1 << (n \/ 2 + 1));\n    t2.reserve(1 << (n \/ 2 + 1));\n    for (int i = 0; i < n \/ 2; ++i)\n      for (int j = t1.size() - 1; j >= 0; --j)\n        t1.push_back(t1[j] + nums[i]);\n    for (int i = n \/ 2; i < n; ++i)\n      for (int j = t2.size() - 1; j >= 0; --j)\n        t2.push_back(t2[j] + nums[i]);\n    set<int> s2(begin(t2), end(t2));\n    for (int x : unordered_set<int>(begin(t1), end(t1))) {\n      auto it = s2.lower_bound(goal - x);\n      if (it != s2.end())\n        ans = min(ans, abs(goal - x - *it));\n      if (it != s2.begin())\n        ans = min(ans, abs(goal - x - *prev(it)));\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer array\u00a0nums\u00a0and an integer\u00a0goal. You want to choose a subsequence of&nbsp;nums&nbsp;such that the sum of its elements is the closest possible&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,42,696],"class_list":["post-8095","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-search","tag-subsets","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8095","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8095"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8095\/revisions"}],"predecessor-version":[{"id":8101,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8095\/revisions\/8101"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8095"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8095"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8095"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}