2959. Number of Possible Sets of Closing Branches LeetCode Solution
In this guide, you will get 2959. Number of Possible Sets of Closing Branches LeetCode Solution with the best time and space complexity. The solution to Number of Possible Sets of Closing Branches problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Number of Possible Sets of Closing Branches solution in C++
- Number of Possible Sets of Closing Branches solution in Java
- Number of Possible Sets of Closing Branches solution in Python
- Additional Resources
Problem Statement of Number of Possible Sets of Closing Branches
There is a company with n branches across the country, some of which are connected by roads. Initially, all branches are reachable from each other by traveling some roads.
The company has realized that they are spending an excessive amount of time traveling between their branches. As a result, they have decided to close down some of these branches (possibly none). However, they want to ensure that the remaining branches have a distance of at most maxDistance from each other.
The distance between two branches is the minimum total traveled length needed to reach one branch from another.
You are given integers n, maxDistance, and a 0-indexed 2D array roads, where roads[i] = [ui, vi, wi] represents the undirected road between branches ui and vi with length wi.
Return the number of possible sets of closing branches, so that any branch has a distance of at most maxDistance from any other.
Note that, after closing a branch, the company will no longer have access to any roads connected to it.
Note that, multiple roads are allowed.
Example 1:
Input: n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]
Output: 5
Explanation: The possible sets of closing branches are:
– The set [2], after closing, active branches are [0,1] and they are reachable to each other within distance 2.
– The set [0,1], after closing, the active branch is [2].
– The set [1,2], after closing, the active branch is [0].
– The set [0,2], after closing, the active branch is [1].
– The set [0,1,2], after closing, there are no active branches.
It can be proven, that there are only 5 possible sets of closing branches.
Example 2:
Input: n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]]
Output: 7
Explanation: The possible sets of closing branches are:
– The set [], after closing, active branches are [0,1,2] and they are reachable to each other within distance 4.
– The set [0], after closing, active branches are [1,2] and they are reachable to each other within distance 2.
– The set [1], after closing, active branches are [0,2] and they are reachable to each other within distance 2.
– The set [0,1], after closing, the active branch is [2].
– The set [1,2], after closing, the active branch is [0].
– The set [0,2], after closing, the active branch is [1].
– The set [0,1,2], after closing, there are no active branches.
It can be proven, that there are only 7 possible sets of closing branches.
Example 3:
Input: n = 1, maxDistance = 10, roads = []
Output: 2
Explanation: The possible sets of closing branches are:
– The set [], after closing, the active branch is [0].
– The set [0], after closing, there are no active branches.
It can be proven, that there are only 2 possible sets of closing branches.
Constraints:
1 <= n <= 10
1 <= maxDistance <= 105
0 <= roads.length <= 1000
roads[i].length == 3
0 <= ui, vi <= n – 1
ui != vi
1 <= wi <= 1000
All branches are reachable from each other by traveling some roads.
Complexity Analysis
- Time Complexity: O(2^n \cdot n^3)
- Space Complexity: O(n^2)
2959. Number of Possible Sets of Closing Branches LeetCode Solution in C++
class Solution {
public:
int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
const int maxMask = 1 << n;
int ans = 0;
for (int mask = 0; mask < maxMask; ++mask)
if (floydWarshall(n, maxDistance, roads, mask) <= maxDistance)
++ans;
return ans;
}
private:
// Returns the maximum distance between any two branches, where the mask
// represents the selected branches.
int floydWarshall(int n, int maxDistanceThreshold, vector<vector<int>>& roads,
int mask) {
int maxDistance = 0;
vector<vector<int>> dist(n, vector<int>(n, maxDistanceThreshold + 1));
for (int i = 0; i < n; ++i)
if (mask >> i & 1)
dist[i][i] = 0;
for (const vector<int>& road : roads) {
const int u = road[0];
const int v = road[1];
const int w = road[2];
if (mask >> u & 1 && mask >> v & 1) {
dist[u][v] = min(dist[u][v], w);
dist[v][u] = min(dist[v][u], w);
}
}
for (int k = 0; k < n; ++k)
if (mask >> k & 1)
for (int i = 0; i < n; ++i)
if (mask >> i & 1)
for (int j = 0; j < n; ++j)
if (mask >> j & 1)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
for (int i = 0; i < n; ++i)
if (mask >> i & 1)
for (int j = i + 1; j < n; ++j)
if (mask >> j & 1)
maxDistance = max(maxDistance, dist[i][j]);
return maxDistance;
}
};
/* code provided by PROGIEZ */2959. Number of Possible Sets of Closing Branches LeetCode Solution in Java
class Solution {
public int numberOfSets(int n, int maxDistance, int[][] roads) {
final int maxMask = 1 << n;
int ans = 0;
for (int mask = 0; mask < maxMask; ++mask)
if (floydWarshall(n, maxDistance, roads, mask) <= maxDistance)
++ans;
return ans;
}
private int floydWarshall(int n, int maxDistanceThreshold, int[][] roads, int mask) {
int maxDistance = 0;
int[][] dist = new int[n][n];
Arrays.stream(dist).forEach(A -> Arrays.fill(A, maxDistanceThreshold + 1));
for (int i = 0; i < n; ++i)
if ((mask >> i & 1) == 1)
dist[i][i] = 0;
for (int[] road : roads) {
final int u = road[0];
final int v = road[1];
final int w = road[2];
if ((mask >> u & 1) == 1 && (mask >> v & 1) == 1) {
dist[u][v] = Math.min(dist[u][v], w);
dist[v][u] = Math.min(dist[v][u], w);
}
}
for (int k = 0; k < n; ++k)
if ((mask >> k & 1) == 1)
for (int i = 0; i < n; ++i)
if ((mask >> i & 1) == 1)
for (int j = 0; j < n; ++j)
if ((mask >> j & 1) == 1)
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
for (int i = 0; i < n; ++i)
if ((mask >> i & 1) == 1)
for (int j = i + 1; j < n; ++j)
if ((mask >> j & 1) == 1)
maxDistance = Math.max(maxDistance, dist[i][j]);
return maxDistance;
}
}
// code provided by PROGIEZ2959. Number of Possible Sets of Closing Branches LeetCode Solution in Python
class Solution:
def numberOfSets(
self,
n: int,
maxDistance: int,
roads: list[list[int]],
) -> int:
return sum(self._floydWarshall(n, maxDistance, roads, mask) <= maxDistance
for mask in range(1 << n))
def _floydWarshall(
self,
n: int,
maxDistanceThreshold: int,
roads: list[list[int]],
mask: int,
) -> list[list[int]]:
"""
Returns the maximum distance between any two branches, where the mask
represents the selected branches.
"""
maxDistance = 0
dist = [[maxDistanceThreshold + 1] * n for _ in range(n)]
for i in range(n):
if mask >> i & 1:
dist[i][i] = 0
for u, v, w in roads:
if mask >> u & 1 and mask >> v & 1:
dist[u][v] = min(dist[u][v], w)
dist[v][u] = min(dist[v][u], w)
for k in range(n):
if mask >> k & 1:
for i in range(n):
if mask >> i & 1:
for j in range(n):
if mask >> j & 1:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
for i in range(n):
if mask >> i & 1:
for j in range(i + 1, n):
if mask >> j & 1:
maxDistance = max(maxDistance, dist[i][j])
return maxDistance
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.