Skip to main content
Talentd

Count Connected Subgraphs with Even Node Sum - Solution & Explanation

HardArrayBit ManipulationDepth-First SearchBreadth-First Search12 min read
Practice this problem

Problem Statement

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:

  • We keep only the nodes in s.
  • We keep only the edges whose two endpoints are both in s.

Return an integer representing the number of non-empty subsets s of nodes in the graph such that:

  • The induced subgraph of s is connected.
  • The sum of node values in 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 <= 13
  • nums[i] is 0 or 1.
  • 0 <= edges.length <= n * (n - 1) / 2
  • edges[i] = [ui, vi]
  • 0 <= ui < vi < n
  • All edges are distinct.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subset EnumerationO(2^n * (n + m))O(n)Very small graphs where n ≤ 20 and simplicity matters
Bitmask Dynamic ProgrammingO(2^n * n)O(2^n)Small graphs where repeated connectivity checks must be optimized
Tree DP with Parity StatesO(n)O(n)Tree structures or problems guaranteeing acyclic graphs

Video Solution

Leetcode 3910 | Count Connected Subgraphs with Even Node Sum | Biweekly contest 181 • CodeWithMeGuys • 326 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Count Connected Subgraphs with Even Node Sum easy or hard?
This problem is generally classified as hard because it combines graph traversal with dynamic programming and parity reasoning. Recognizing that only two parity states are needed is the key observation that makes the optimal solution manageable.
Count Connected Subgraphs with Even Node Sum Python/Java solution
Most implementations perform a DFS and maintain two counters per node representing even and odd parity subgraphs. Python solutions typically use recursion with adjacency lists, while Java versions often store DP states in arrays or small objects during traversal.
How to solve Count Connected Subgraphs with Even Node Sum in O(n)?
Use a DFS-based tree DP where each node maintains two counts: subgraphs including that node with even sum and with odd sum. Initialize based on the node value parity, then merge children contributions using parity transitions. Each merge step is constant time, leading to linear complexity.
What is the best approach for Count Connected Subgraphs with Even Node Sum?
The most efficient approach uses tree dynamic programming with parity states. During a DFS traversal, each node tracks the number of connected subgraphs including that node with even and odd sums. Child results are merged using parity rules, producing an overall O(n) time and O(n) space solution for tree graphs.
Is Count Connected Subgraphs with Even Node Sum asked at Google/Amazon/Meta?
Variants of connected subgraph counting and tree DP problems appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. The parity-based counting technique is a common extension used to test deeper dynamic programming understanding.
What data structure is used in Count Connected Subgraphs with Even Node Sum?
The main structure is an adjacency list representing the graph or tree. The algorithm relies on DFS traversal combined with dynamic programming states that track even and odd parity counts for each node.
What is the time complexity of Count Connected Subgraphs with Even Node Sum?
The optimal tree DP solution runs in O(n) time because each node and edge is processed once during DFS merging. Brute force enumeration requires O(2^n * (n + m)) since every subset must be checked for connectivity and sum parity.

Ready to solve this problem?

Practice Count Connected Subgraphs with Even Node Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays