Count Non Adjacent Subsets in a Rooted Tree - Video Solutions
Leetcode 3939 | Count Non Adjacent Subsets in a Rooted Tree | Leetcode biweekly 183 | DP on Trees
Count Non Adjacent Subsets in a Rooted Tree - Video Solution
Watch the video solution for Count Non Adjacent Subsets in a Rooted Tree, a hard level problem involving Array, Dynamic Programming, Tree. This walkthrough by CodeWithMeGuys has 575 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a rooted tree with n nodes labeled from 0 to n - 1, represented by an integer array parent of length n, where:
parent[0] = -1(node 0 is the root).- For each
1 <= i < n,parent[i]is the parent of nodei(0 <= parent[i] < i).
You are also given an integer array nums of length n, where nums[i] is the value of node i, and an integer k.
A non-empty subset of nodes is called valid if:
- The sum of the values of the selected nodes is divisible by
k. - No two selected nodes are adjacent in the tree (no node and its direct parent are both included in the subset).
Return the number of valid subsets modulo 109 + 7.
Example 1:
Input: parent = [-1,0,1], nums = [1,2,3], k = 3
Output: 1
Explanation:
The only valid subset is {2}. It contains node 2 with value 3, which is divisible by 3.
Example 2:
Input: parent = [-1,0,0,0], nums = [2,1,2,1], k = 3
Output: 2
Explanation:
The valid subsets are:
{1, 2}: Nodes 1 and 2 are both children of node 0 and not directly connected to each other. Their values sum to1 + 2 = 3, which is divisible by 3.{2, 3}: Nodes 2 and 3 are also non-adjacent. Their values sum to2 + 1 = 3, which is divisible by 3.
No other subset satisfies both conditions. Therefore, the answer is 2.
Constraints:
n == parent.length == nums.length1 <= n <= 1000parent[0] == -1- For all
1 <= i < n:0 <= parent[i] < i
1 <= nums[i] <= 1091 <= k <= 100parentdescribes a valid rooted tree.
Approach Overview
Problem Overview: Given a rooted tree, count how many subsets of nodes can be selected such that no two chosen nodes share a parent–child relationship. In graph terms, this asks for the number of independent sets in a tree.
Approach 1: Brute Force Subset Enumeration (O(2^n * n) time, O(n) space)
Generate every subset of nodes and check whether it contains an adjacent pair. For each subset, iterate through nodes and verify that no node and its parent are both selected. This guarantees correctness but becomes infeasible quickly because a tree with n nodes has 2^n possible subsets. Useful only for very small trees or for validating optimized solutions during testing.
Approach 2: Backtracking with Pruning (O(2^n) worst case, O(n) space)
Traverse nodes and decide whether to include or exclude each one. If you include a node, you must forbid selecting its parent and children. Maintaining a visited or restricted set allows pruning branches early. This reduces some redundant checks compared to full subset enumeration but still explores an exponential search space. Works for small trees where constraints allow aggressive pruning.
Approach 3: Tree Dynamic Programming with DFS (O(n) time, O(n) space)
The optimal solution uses dynamic programming on the tree structure. For each node u, compute two values: dp[u][0] (number of valid subsets in the subtree when u is excluded) and dp[u][1] (when u is included). If u is included, none of its children can be included, so multiply the dp[v][0] values of all children v. If u is excluded, each child can be either included or excluded, so multiply dp[v][0] + dp[v][1]. Compute these values using a depth‑first traversal of the tree with DFS. This structure works because trees have no cycles, making subtrees independent. The final answer is dp[root][0] + dp[root][1]. This technique is a classic example of tree DP.
Recommended for interviews: The DFS + tree DP approach. Interviewers expect you to recognize that the constraint "no adjacent nodes" maps directly to the independent set problem on trees. Starting from a brute force explanation shows you understand the constraint, but deriving the include/exclude DP demonstrates strong problem‑solving skills and knowledge of tree dynamic programming.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^n * n) | O(n) | Very small trees or verifying correctness during testing |
| Backtracking with Pruning | O(2^n) | O(n) | Small input sizes where pruning significantly reduces the search space |
| Tree DP with DFS | O(n) | O(n) | General case and interview settings; optimal for large trees |