You are given an undirected graph with n nodes labeled from 0 to n - 1. Node i has a value of nums[i], which is either 0 or 1. The edges of the graph are given by a 2D array edges where edges[i] = [ui, vi] represents an edge between node ui and node vi.
For a non-empty subset s of nodes in the graph, we consider the induced subgraph of s generated as follows:
s.s.Return an integer representing the number of non-empty subsets s of nodes in the graph such that:
s is connected.s is even.
Example 1:
Input: nums = [1,0,1], edges = [[0,1],[1,2]]
Output: 2
Explanation:
s |
connected? | sum of node values | counted? |
|---|---|---|---|
[0] |
Yes | 1 | No |
[1] |
Yes | 0 | Yes |
[2] |
Yes | 1 | No |
[0,1] |
Yes | 1 | No |
[0,2] |
No, node 0 and node 2 are disconnected. | 2 | No |
[1,2] |
Yes | 1 | No |
[0,1,2] |
Yes | 2 | Yes |
Example 2:
Input: nums = [1], edges = []
Output: 0
Explanation:
s |
connected? | sum of node values | counted? |
|---|---|---|---|
[0] |
Yes | 1 | No |
Constraints:
1 <= n == nums.length <= 13nums[i] is 0 or 1.0 <= edges.length <= n * (n - 1) / 2edges[i] = [ui, vi]0 <= ui < vi < nProblem 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.
Notice that the number of nodes in the problem does not exceed 13, so we can enumerate all non-empty subsets s of nodes. For each subset, we calculate the total sum of node values and check whether its induced subgraph is connected.
Specifically, we can use an integer sub to represent the subset s, where the i-th bit of sub is 1 if node i is in the subset, and 0 otherwise. For each subset, we first compute the sum of its node values. If the sum is odd, we skip this subset; otherwise, we use DFS to check whether the induced subgraph is connected. We can use an integer vis to represent the visited nodes: initially, the i-th bit of vis is 1 if node i is not in the subset, and 0 if node i is in the subset. We start DFS from any node in subset s, visit all its adjacent nodes, and mark visited nodes in vis as 1. Finally, if all bits in vis are 1, it means the induced subgraph of subset s is connected, so we increment the answer by 1.
The time complexity is O(2^n times (n + m)) and the space complexity is O(n + m), where n and m are the number of nodes and edges, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^n * (n + m)) | O(n) | Very small graphs where n ≤ 20 and simplicity matters |
| Bitmask Dynamic Programming | O(2^n * n) | O(2^n) | Small graphs where repeated connectivity checks must be optimized |
| Tree DP with Parity States | O(n) | O(n) | Tree structures or problems guaranteeing acyclic graphs |
Leetcode 3910 | Count Connected Subgraphs with Even Node Sum | Biweekly contest 181 • CodeWithMeGuys • 326 views views
Watch 4 more video solutions →Practice Count Connected Subgraphs with Even Node Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor