{"id":4871,"date":"2019-02-17T01:02:43","date_gmt":"2019-02-17T09:02:43","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4871"},"modified":"2020-01-29T21:14:41","modified_gmt":"2020-01-30T05:14:41","slug":"leetcode-996-number-of-squareful-arrays","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-996-number-of-squareful-arrays\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 996. Number of Squareful Arrays"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-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 Weekly Contest 124 (993, 994, 995, 996) - \u5237\u9898\u627e\u5de5\u4f5c\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/ISnktonx7rY?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>Given an array&nbsp;<code>A<\/code>&nbsp;of non-negative integers, the array is&nbsp;<em>squareful<\/em>&nbsp;if for every pair of adjacent elements, their sum is a perfect square.<\/p>\n\n\n\n<p>Return the number of permutations of A that are squareful.&nbsp; Two permutations&nbsp;<code>A1<\/code>&nbsp;and&nbsp;<code>A2<\/code>&nbsp;differ if and only if there is some index&nbsp;<code>i<\/code>&nbsp;such that&nbsp;<code>A1[i] != A2[i]<\/code>.<\/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>[1,17,8]\n<strong>Output: <\/strong>2\n<strong>Explanation: <\/strong>\n[1,8,17] and [17,8,1] are the valid permutations.\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>[2,2,2]\n<strong>Output: <\/strong>1\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>1 &lt;= A.length &lt;= 12<\/code><\/li><li><code>0 &lt;= A[i] &lt;= 1e9<\/code><\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution1:&nbsp;DFS<\/strong><\/h2>\n\n\n\n<p>Try all permutations with pruning.<\/p>\n\n\n\n<p>Time complexity: O(n!)<br>Space complexity: O(n)<\/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, running time: 4 ms, 8.8 MB\nclass Solution {\npublic:\n  int numSquarefulPerms(vector<int>& A) {\n    std::sort(begin(A), end(A));\n    vector<int> cur;\n    vector<int> used(A.size());\n    int ans = 0;\n    dfs(A, cur, used, ans);\n    return ans;\n  }\nprivate:\n  bool squareful(int x, int y) {\n    int s = sqrt(x + y);\n    return s * s == x + y;\n  }\n  \n  void dfs(const vector<int>& A, vector<int>& cur, vector<int>& used, int& ans) {    \n    if (cur.size() == A.size()) {\n      ++ans;\n      return;\n    }\n    for (int i = 0; i < A.size(); ++i) {\n      if (used[i]) continue;\n      \/\/ Avoid duplications.\n      if (i > 0 && !used[i - 1] && A[i] == A[i - 1]) continue; \n      \/\/ Prune invalid solutions.\n      if (!cur.empty() && !squareful(cur.back(), A[i])) continue;\n      \n      cur.push_back(A[i]);\n      used[i] = 1;\n      dfs(A, cur, used, ans);\n      used[i] = 0;\n      cur.pop_back();\n    }\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2:&nbsp;DP&nbsp;Hamiltonian&nbsp;Path<\/strong><\/h2>\n\n\n\n<p>dp[s][i] := # of ways to reach state s (binary mask of nodes visited) that ends with node i<\/p>\n\n\n\n<p>dp[s | (1 &lt;&lt; j)][j] += dp[s][i] if g[i][j]<\/p>\n\n\n\n<p>Time complexity: O(n^2*2^n)<br>Space complexity: O(2^n)<\/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, running time: 20 ms, 14.9 MB\nclass Solution {\npublic:\n  int numSquarefulPerms(vector<int>& A) {\n    const int n = A.size();\n    \/\/ For deduplication.\n    std::sort(begin(A), end(A));        \n    \/\/ g[i][j] == 1 if A[i], A[j] are squareful.\n    vector<vector<int>> g(n, vector<int>(n)); \n    \/\/ dp[s][i] := number of ways to reach state s and ends with node i.\n    vector<vector<int>> dp(1 << n, vector<int>(n)); \n\n    for (int i = 0; i < n; ++i) {      \n      for (int j = 0; j < n; ++j) {\n        if (i == j) continue;\n        int r = sqrt(A[i] + A[j]);\n        if (r * r == A[i] + A[j])\n          g[i][j] = 1;\n      }\n    }\n    \n    \/\/ For the same numbers, only the first one can be the starting point.\n    for (int i = 0; i < n; ++i)\n      if (i == 0 || A[i] != A[i - 1])\n        dp[(1 << i)][i] = 1;    \n    \n    int ans = 0;\n    for (int s = 0; s < (1 << n); ++s)\n      for (int i = 0; i < n; ++i) {\n        if (!dp[s][i]) continue;\n        for (int j = 0; j < n; ++j) {\n          if (!g[i][j]) continue;\n          if (s &#038; (1 << j)) continue;\n          \/\/ Only the first one can be used as the dest.\n          if (j > 0 && !(s & (1 << (j - 1))) &#038;&#038; A[j - 1] == A[j]) continue;\n          dp[s | (1 << j)][j] += dp[s][i];\n        }\n      }\n    \n    for (int i = 0; i < n; ++i)\n      ans += dp[(1 << n) - 1][i];\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Related Problems<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-943-find-the-shortest-superstring\/\">https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-943-find-the-shortest-superstring\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-980-unique-paths-iii\/\">https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-980-unique-paths-iii\/<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Given an array&nbsp;A&nbsp;of non-negative integers, the array is&nbsp;squareful&nbsp;if for every pair of adjacent elements, their sum is a perfect square. Return the number of permutations&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76,44],"tags":[33,437,42],"class_list":["post-4871","post","type-post","status-publish","format-standard","hentry","category-graph","category-searching","tag-dfs","tag-hamiltonian-path","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4871","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=4871"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4871\/revisions"}],"predecessor-version":[{"id":6185,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4871\/revisions\/6185"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4871"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4871"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4871"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}