C++ dpWithBitMask Step By Step Explanation 90% Faster O(N*2^N)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->O(n*2^n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->O(2^n)\n\n# Code\n```\nclass Solution {\npublic:\n   //Function to find Distance of all nodes from a given node.->o(n)\n   //This function is called for each node.->o(n*n)\n    vector<int>findDistance(vector<vector<int>>&adj,int node){\n        int n=adj.size();\n        vector<int>ans(n);\n        ans[node]=0;\n        queue<pair<int,int>>q;\n        q.push({node,-1});\n        while(!q.empty()){\n            int curr_node=q.front().first;\n            int parent=q.front().second;\n            q.pop();\n            for(auto &j:adj[curr_node]){\n                if(j!=parent){\n                    ans[j]=ans[curr_node]+1;\n                    q.push({j,curr_node});\n                }\n            }\n        }\n        return ans;\n    }\n    //Function To check that the nodes present in mask forms a Subtree.->o(setBits in mask) for calls + o(n) for adjacency list in total.\n    bool isValidSubTree(vector<vector<int>>&adj,int originalMask,int &mask,int curr_node){\n        mask=mask|(1<<curr_node);\n        if(mask==originalMask)return true;\n        for(auto &j:adj[curr_node]){\n            if((originalMask&(1<<j)) && (!(mask&(1<<j)))){\n                if(isValidSubTree(adj,originalMask,mask,j)){\n                    return true;\n                }\n            }\n        }\n        return false;\n\n    } \n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n        \n        //Graph->o(n+E),where E=n-1;\n        vector<vector<int>>adj(n);\n        for(int i=0;i<n-1;i++){\n            int u=edges[i][0];\n            int v=edges[i][1];\n            adj[u-1].push_back(v-1);\n            adj[v-1].push_back(u-1);\n        }\n        //Calculating a 2D (n*n) distance matrix->o(n*n)\n        vector<vector<int>>dist(n);\n        for(int i=0;i<n;i++){\n           dist[i]=findDistance(adj,i);\n        }\n        vector<int>dp(1<<n);\n        vector<bool>mark(1<<n);\n        //O(n*2^n)\n        for(int mask=1;mask<(1<<n);mask++){\n            int bits=__builtin_popcount(mask);\n            //There must be two nodes to get distance 1.\n            if(bits<2){\n                continue;\n            }\n            int curr_Mask=0;\n            int lastSetbit=0;\n            for(int j=0;j<n;j++){\n                if(mask&(1<<j)){\n                    lastSetbit=j;\n                    break;\n                }\n            }\n            //if mask is subtree mark it.\n            if(isValidSubTree(adj,mask,curr_Mask,lastSetbit)){\n               mark[mask]=1;\n            }\n            //check max Distance for Subtree ...using dp->\n            int maxDistance=0;\n            //just remove a node ans for remaining combination node is precalculated\n                if((mask&(1<<lastSetbit))){\n                    int newMask=(mask^(1<<lastSetbit));\n                     maxDistance=max(dp[newMask],maxDistance);\n                     // check the distance of all nodes due to removed node and calculate the final ans\n                     for(int k=0;k<n;k++){\n                        if(newMask&(1<<k)){\n                            maxDistance=max(maxDistance,dist[lastSetbit][k]);\n                        }\n                     }    \n                }\n         \n            dp[mask]=maxDistance;\n        }\n        vector<int>result(n-1);\n        //if mask is validSubTree and maxDistance is AtLeast 1 .Then ,store it in result\n        for(int mask=1;mask<(1<<n);mask++){\n                if(dp[mask] && mark[mask]){\n                    result[dp[mask]-1]++;\n                }  \n        }\n        return result;\n    }\n};\n```
['Dynamic Programming', 'Tree', 'Bitmask', 'C++']