Number of Squareful Arrays Solutions in C++

/// Source : https://leetcode.com/problems/number-of-squareful-arrays/
/// Author : liuyubobobo
/// Time   : 2019-02-16

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_set>

using namespace std;


/// Backtrack
/// Using string hash to record the same value
/// Time Complexity: O(n^n)
/// Space Complexity: O(n)
class Solution {

private:
    int n;

public:
    int numSquarefulPerms(vector<int>& A) {

        n = A.size();
        vector<vector<int>> ok(n);
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                if(j != i && perfectSquare(A[i] + A[j]))
                    ok[i].push_back(j);

        int res = 0;
        unordered_set<string> hashset;
        for(int i = 0; i < n; i ++){
            vector<bool> visited(n, false);
            visited[i] = true;

            vector<int> seqindex = {i};

            string hash = to_string(A[i]);
            hashset.insert(hash);

            res += dfs(A, ok, 1, seqindex, hash, visited, hashset);
        }
        return res;
    }

private:
    int dfs(const vector<int>& A, const vector<vector<int>>& ok,
            int index, vector<int>& seqindex, const string& hash, vector<bool>& visited,
            unordered_set<string>& hashset){

        if(index == n)
            return 1;

        int res = 0;
        for(int next: ok[seqindex[index - 1]])
            if(!visited[next]){

                string newhash = hash + "#" + to_string(A[next]);
                if(!hashset.count(newhash)){
                    hashset.insert(newhash);

                    seqindex.push_back(next);
                    visited[next] = true;
                    res += dfs(A, ok, index + 1, seqindex, newhash, visited, hashset);
                    visited[next] = false;
                    seqindex.pop_back();
                }
            }
        return res;
    }

    bool perfectSquare(int x){
        int t = sqrt(x);
        return t * t == x;
    }
};


int main() {

    vector<int> A1 = {1, 17, 8};
    cout << Solution().numSquarefulPerms(A1) << endl;
    // 2

    vector<int> A2 = {2, 2, 2};
    cout << Solution().numSquarefulPerms(A2) << endl;
    // 1

    vector<int> A3(12, 0);
    cout << Solution().numSquarefulPerms(A3) << endl;
    // 1

    return 0;
}

/// Source : https://leetcode.com/problems/number-of-squareful-arrays/
/// Author : liuyubobobo
/// Time   : 2019-02-19

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>

using namespace std;


/// Backtrack
/// Using HashMap to record the same value
/// Time Complexity: O(n^n)
/// Space Complexity: O(n)
class Solution {

private:
    int n;

public:
    int numSquarefulPerms(vector<int>& A) {

        n = A.size();
        unordered_map<int, int> freq;
        unordered_set<int> elements;
        for(int e: A){
            freq[e] ++;
            elements.insert(e);
        }

        unordered_map<int, unordered_set<int>> g;
        for(int i = 0; i < n; i ++)
            for(int j = i + 1; j < n; j ++)
                if(perfectSquare(A[i] + A[j])){
                    g[A[i]].insert(A[j]);
                    g[A[j]].insert(A[i]);
                }

        int res = 0;
        for(int e: elements){
            freq[e] --;
            res += dfs(g, e, 1, freq);
            freq[e] ++;
        }
        return res;
    }

private:
    int dfs(unordered_map<int, unordered_set<int>>& g,
            int e, int index, unordered_map<int, int>& freq){

        if(index == n)
            return 1;

        int res = 0;
        for(int next: g[e])
            if(freq[next]){
                freq[next] --;
                res += dfs(g, next, index + 1, freq);
                freq[next] ++;
            }
        return res;
    }

    bool perfectSquare(int x){
        int t = sqrt(x);
        return t * t == x;
    }
};


int main() {

    vector<int> A1 = {1, 17, 8};
    cout << Solution().numSquarefulPerms(A1) << endl;
    // 2

    vector<int> A2 = {2, 2, 2};
    cout << Solution().numSquarefulPerms(A2) << endl;
    // 1

    vector<int> A3(12, 0);
    cout << Solution().numSquarefulPerms(A3) << endl;
    // 1

    return 0;
}

/// Source : https://leetcode.com/problems/number-of-squareful-arrays/
/// Author : liuyubobobo
/// Time   : 2019-02-19

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>

using namespace std;


/// Memory Search
/// Divide corresponding factorial number to avoid repeating counting :-)
/// Time Complexity: O(n*2^n)
/// Space Complexity: O(n*2^n)
class Solution {

private:
    int n;

public:
    int numSquarefulPerms(vector<int>& A) {

        n = A.size();

        vector<vector<int>> g(n);
        for(int i = 0; i < n; i ++)
            for(int j = i + 1; j < n; j ++)
                if(perfectSquare(A[i] + A[j])){
                    g[i].push_back(j);
                    g[j].push_back(i);
                }

        int res = 0;
        vector<vector<int>> dp(n, vector<int>(1 << n, -1));
        for(int i = 0; i < n; i ++)
            res += dfs(g, i, 1 << i, dp);

        unordered_map<int, int> freq;
        for(int e: A) freq[e] ++;
        for(const pair<int, int>& p: freq) res /= fac(p.second);
        return res;
    }

private:
    int dfs(const vector<vector<int>>& g,
            int index, int visited, vector<vector<int>>& dp){

        if(visited == (1 << n) - 1)
            return 1;

        if(dp[index][visited] != -1) return dp[index][visited];

        int res = 0;
        for(int next: g[index])
            if(!(visited & (1 << next))){
                visited += (1 << next);
                res += dfs(g, next, visited, dp);
                visited -= (1 << next);
            }
        return dp[index][visited] = res;
    }

    int fac(int x){
        if(x == 0 || x == 1) return 1;
        return x * fac(x - 1);
    }

    bool perfectSquare(int x){
        int t = sqrt(x);
        return t * t == x;
    }
};


int main() {

    vector<int> A1 = {1, 17, 8};
    cout << Solution().numSquarefulPerms(A1) << endl;
    // 2

    vector<int> A2 = {2, 2, 2};
    cout << Solution().numSquarefulPerms(A2) << endl;
    // 1

    vector<int> A3(12, 0);
    cout << Solution().numSquarefulPerms(A3) << endl;
    // 1

    return 0;
}