复杂度分析

• 时间复杂度： O(N*2^N)，其中 N 是 A 的长度。

• 空间复杂度： O(N*2^N)。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static const int N = 12 + 1;
    std::unordered_set<int> st;
    int dp[N][1 << N];

    int dfs(int v, int state, const vector<int> &A) {
        // 递归的边界
        if ((1 << v) == state) return 1;
        // 记忆化
        if (dp[v][state] != -1) return dp[v][state];

        int ret = 0, n = A.size();
        std::unordered_set<int> used;    
        for (int u = 0; u < n; ++u) {
            if (((1 << u) & state) && u != v && st.find(A[u] + A[v]) != st.end() && used.find(A[u]) == used.end()) {
                used.insert(A[u]);
                ret += dfs(u, state - (1 << v), A);
            }
        }
        return dp[v][state] = ret;
    }
    int numSquarefulPerms(vector<int>& A) {
        ...