{"id":1587,"date":"2018-01-09T22:13:49","date_gmt":"2018-01-10T06:13:49","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1587"},"modified":"2018-09-03T22:17:59","modified_gmt":"2018-09-04T05:17:59","slug":"leetcode-494-target-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-494-target-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 494. Target Sum"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 494. Target Sum \u4e0a - \u5237\u9898\u627e\u5de5\u4f5c EP156\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/r6Wz4W1TbuI?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><\/p>\n<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 494. Target Sum \u4e0b - \u5237\u9898\u627e\u5de5\u4f5c EP157\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/zks6mN06xdQ?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><\/p>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e32\u6570\u5b57\uff0c\u4f60\u53ef\u4ee5\u5728\u6bcf\u4e2a\u6570\u5b57\u524d\u653e\u7f6e+\u6216-\uff0c\u95ee\u6709\u591a\u5c11\u79cd\u65b9\u6cd5\u53ef\u4ee5\u4f7f\u5f97\u8868\u8fbe\u5f0f\u7684\u503c\u7b49\u4e8etarget\u3002You are given a list of non-negative integers, a1, a2, &#8230;, an, and a target, S. Now you have 2 symbols\u00a0<code>+<\/code>\u00a0and\u00a0<code>-<\/code>. For each integer, you should choose one from\u00a0<code>+<\/code>\u00a0and\u00a0<code>-<\/code>\u00a0as its new symbol.<\/p>\n<p>Find out how many ways to assign symbols to make sum of integers equal to target S.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"\">Input: nums is [1, 1, 1, 1, 1], S is 3. \r\nOutput: 5\r\nExplanation: \r\n\r\n-1+1+1+1+1 = 3\r\n+1-1+1+1+1 = 3\r\n+1+1-1+1+1 = 3\r\n+1+1+1-1+1 = 3\r\n+1+1+1+1-1 = 3\r\n\r\nThere are 5 ways to assign symbols to make the sum of nums be target 3.\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>The length of the given array is positive and will not exceed 20.<\/li>\n<li>The sum of elements in the given array will not exceed 1000.<\/li>\n<li>Your output answer is guaranteed to be fitted in a 32-bit integer.<\/li>\n<\/ol>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<h1><strong>Idea:\u00a0DP<\/strong><\/h1>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1598\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1599\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1597\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1609\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-4.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1608\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-5.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-5.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-5-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-5-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1607\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-6.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-6.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-6-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-6-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1606\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-7.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-7.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-7-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/494-ep156-7-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><br \/>\n<\/ins><\/p>\n<h1><strong>Solution 1: DP<\/strong><\/h1>\n<p>Time complexity: O(n*sum)<\/p>\n<p>Space complexity: O(n*sum)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 16 ms\r\nclass Solution {\r\npublic:\r\n    int findTargetSumWays(vector&lt;int&gt;&amp; nums, int S) {\r\n      const int n = nums.size();\r\n      const int sum = std::accumulate(nums.begin(), nums.end(), 0);\r\n      if (sum &lt; S) return 0;\r\n      const int offset = sum;\r\n      \/\/ ways[i][j] means total ways to sum up to (j - offset) using nums[0] ~ nums[i - 1].\r\n      vector&lt;vector&lt;int&gt;&gt; ways(n + 1, vector&lt;int&gt;(sum + offset + 1, 0));\r\n      ways[0][offset] = 1;\r\n      for (int i = 0; i &lt; n; ++i) {\r\n        for (int j = nums[i]; j &lt; 2 * sum + 1 - nums[i]; ++j)\r\n          if (ways[i][j]) {\r\n            ways[i + 1][j + nums[i]] += ways[i][j];\r\n            ways[i + 1][j - nums[i]] += ways[i][j];\r\n          }        \r\n      }\r\n      \r\n      return ways.back()[S + offset];\r\n    }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ SC O(n)<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 12 ms\r\nclass Solution {\r\npublic:\r\n    int findTargetSumWays(vector&lt;int&gt;&amp; nums, int S) {\r\n      const int n = nums.size();\r\n      const int sum = std::accumulate(nums.begin(), nums.end(), 0);\r\n      if (sum &lt; std::abs(S)) return 0;\r\n      const int kOffset = sum;\r\n      const int kMaxN = sum * 2 + 1;\r\n      vector&lt;int&gt; ways(kMaxN, 0);      \r\n      ways[kOffset] = 1;\r\n      for (int num : nums) {\r\n        vector&lt;int&gt; tmp(kMaxN, 0);\r\n        for (int i = num; i &lt; kMaxN - num; ++i)\r\n          if (ways[i]) {\r\n            tmp[i + num] += ways[i];\r\n            tmp[i - num] += ways[i];\r\n          }\r\n        std::swap(ways, tmp);\r\n      }      \r\n      return ways[S + kOffset];\r\n    }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 28 ms\r\nclass Solution {\r\n  public int findTargetSumWays(int[] nums, int S) {\r\n    int sum = 0;\r\n    for (final int num : nums)\r\n      sum += num;\r\n    if (sum &lt; S) return 0;\r\n    final int kOffset = sum;\r\n    final int kMaxN = sum * 2 + 1;\r\n    int[] ways = new int[kMaxN];\r\n    ways[kOffset] = 1;\r\n    for (final int num : nums) {      \r\n      int[] tmp = new int[kMaxN];      \r\n      for (int i = num; i &lt; kMaxN - num; ++i) {\r\n        tmp[i + num] += ways[i];\r\n        tmp[i - num] += ways[i];\r\n      }\r\n      ways = tmp;\r\n    }\r\n    return ways[S + kOffset];\r\n  }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ \/ V2<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 17 ms\r\nclass Solution {\r\npublic:\r\n    int findTargetSumWays(vector&lt;int&gt;&amp; nums, int S) {\r\n      const int n = nums.size();\r\n      const int sum = std::accumulate(nums.begin(), nums.end(), 0);\r\n      if (sum &lt; std::abs(S)) return 0;\r\n      const int kOffset = sum;\r\n      const int kMaxN = sum * 2 + 1;\r\n      vector&lt;int&gt; ways(kMaxN, 0);      \r\n      ways[kOffset] = 1;\r\n      for (int num : nums) {\r\n        vector&lt;int&gt; tmp(kMaxN, 0);\r\n        for (int i = 0; i &lt; kMaxN; ++i) {\r\n          if (i + num &lt; kMaxN) tmp[i] += ways[i + num];\r\n          if (i - num &gt;= 0)    tmp[i] += ways[i - num];\r\n        }\r\n        std::swap(ways, tmp);\r\n      }\r\n      return ways[S + kOffset];\r\n    }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2:\u00a0DFS<\/strong><\/h1>\n<p>Time complexity: O(2^n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 422 ms\r\nclass Solution {\r\npublic:\r\n  int findTargetSumWays(vector&lt;int&gt;&amp; nums, int S) {\r\n    const int sum = std::accumulate(nums.begin(), nums.end(), 0);\r\n    if (sum &lt; std::abs(S)) return 0;\r\n    int ans = 0;\r\n    dfs(nums, 0, S, ans);\r\n    return ans;\r\n  }\r\nprivate:\r\n  void dfs(const vector&lt;int&gt;&amp; nums, int d, int S, int&amp; ans) {\r\n    if (d == nums.size()) {\r\n      if (S == 0) ++ans;\r\n      return;\r\n    }    \r\n    dfs(nums, d + 1, S - nums[d], ans);\r\n    dfs(nums, d + 1, S + nums[d], ans);\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 615 ms\r\nclass Solution {\r\n  private int ans;\r\n  public int findTargetSumWays(int[] nums, int S) {\r\n    int sum = 0;\r\n    for (final int num : nums)\r\n      sum += num;\r\n    if (sum &lt; Math.abs(S)) return 0;\r\n    ans = 0;\r\n    dfs(nums, 0, S);\r\n    return ans;\r\n  }\r\n  \r\n  private void dfs(int[] nums, int d, int S) {\r\n    if (d == nums.length) {\r\n      if (S == 0) ++ans;\r\n      return;\r\n    }\r\n    dfs(nums, d + 1, S - nums[d]);\r\n    dfs(nums, d + 1, S + nums[d]);\r\n  }\r\n}<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 3:\u00a0Subset sum<\/strong><\/h1>\n<p>Time complexity: O(n*sum)<\/p>\n<p>Space complexity: O(sum)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++ w\/ copy<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 7 ms\r\nclass Solution {\r\npublic:\r\n    int findTargetSumWays(vector&lt;int&gt;&amp; nums, int S) {\r\n      S = std::abs(S);      \r\n      const int sum = std::accumulate(nums.begin(), nums.end(), 0);\r\n      if (sum &lt; S || (S + sum) % 2 != 0) return 0;\r\n      const int target = (S + sum) \/ 2;\r\n      vector&lt;int&gt; dp(target + 1, 0);\r\n      dp[0] = 1;\r\n      for (int num : nums) {\r\n        vector&lt;int&gt; tmp(dp);\r\n        for (int j = 0; j &lt;= target - num; ++j)\r\n          tmp[j + num] += dp[j];\r\n        std::swap(dp, tmp);\r\n      }\r\n      \r\n      return dp[target];\r\n    }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++  w\/o copy<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 6 ms\r\nclass Solution {\r\npublic:\r\n    int findTargetSumWays(vector&lt;int&gt;&amp; nums, int S) {\r\n      S = std::abs(S);\r\n      const int n = nums.size();\r\n      const int sum = std::accumulate(nums.begin(), nums.end(), 0);\r\n      if (sum &lt; S || (S + sum) % 2 != 0) return 0;\r\n      const int target = (S + sum) \/ 2;\r\n      vector&lt;int&gt; dp(target + 1, 0);\r\n      dp[0] = 1;\r\n      for (int num : nums)\r\n        for (int j = target; j &gt;= num; --j)\r\n          dp[j] += dp[j - num];\r\n      \r\n      return dp[target];\r\n    }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e32\u6570\u5b57\uff0c\u4f60\u53ef\u4ee5\u5728\u6bcf\u4e2a\u6570\u5b57\u524d\u653e\u7f6e+\u6216-\uff0c\u95ee\u6709\u591a\u5c11\u79cd\u65b9\u6cd5\u53ef\u4ee5\u4f7f\u5f97\u8868\u8fbe\u5f0f\u7684\u503c\u7b49\u4e8etarget\u3002You are given a list of non-negative integers, a1, a2, &#8230;, an, and a target, S. Now you have 2 symbols\u00a0+\u00a0and\u00a0-. For each integer, you&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46,164],"tags":[122,33,62,211],"class_list":["post-1587","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","category-medium","tag-combination","tag-dfs","tag-sum","tag-target","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1587","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=1587"}],"version-history":[{"count":20,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1587\/revisions"}],"predecessor-version":[{"id":3842,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1587\/revisions\/3842"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1587"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1587"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}