Count Connected Subgraphs with Even Node Sum - Solution & Explanation

Problem Overview: You are given a graph where each node has a value. The task is to count how many connected subgraphs have a total node-value sum that is even. A valid subgraph must remain connected, so arbitrary subsets of nodes are not allowed unless the edges between them keep the structure connected.

Approach 1: Brute Force Enumeration (O(2^n * (n + m)) time, O(n) space)

Generate every possible subset of nodes using bitmasks. For each subset, check if it forms a connected component using a BFS/DFS over the original graph restricted to those nodes. If the subset is connected, compute the sum of node values and check whether the parity is even. This approach directly models the definition of the problem but becomes impractical quickly because there are 2^n subsets. It works only for very small graphs (typically n ≤ 20). Connectivity checking uses a standard traversal from DFS or BFS.

Approach 2: Bitmask DP for Small Graphs (O(2^n * n) time, O(2^n) space)

If the graph size is small, dynamic programming over subsets can reduce repeated connectivity checks. Maintain a DP state for each mask that stores whether the subset is connected and its parity sum. Build masks incrementally by adding one node and verifying that it connects to at least one node already in the mask. Use bit operations to update the parity of the sum. This reduces redundant graph traversals but still scales exponentially. Bitmask DP appears frequently in graph problems where n is constrained.

Approach 3: Tree DP with Parity Merging (O(n) time, O(n) space)

When the graph is a tree (the most common interview variant), you can count connected subgraphs using a bottom-up DFS. For each node u, maintain two values: the number of connected subgraphs in its subtree that include u with even sum, and with odd sum. Start with the node’s own value parity. While processing children, merge their contributions using parity rules: combining two subgraphs flips parity when one side is odd. Each merge step resembles subset convolution but only across two parity states, so it remains constant time. The DFS accumulates results for all nodes while counting valid even-sum subgraphs. This technique relies on dynamic programming over tree structure.

Recommended for interviews: The brute force method shows you understand the definition of connected subgraphs, but interviewers expect the tree DP optimization when the input is a tree. Tracking only two parity states (even/odd) dramatically simplifies the state space and leads to an O(n) traversal. Demonstrating how parity merges across children is the key insight that signals strong graph and DP fundamentals.