Number of Possible Sets of Closing Branches

Number of Possible Sets of Closing Branches - Problem

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] = [u_i, v_i, w_i] represents the undirected road between branches u_i and v_i with length w_i.

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,1]]

› Output: 5

💡 Note: Valid subsets: {0}, {1}, {2}, {0,1}, {0,2}. Subset {1,2} invalid (distance 10 > 5). Subset {0,1,2} invalid (distance 10 > 5).

Example 2 — All Connected Within Distance

$ Input: n = 3, maxDistance = 10, roads = [[0,1,1],[1,2,1],[2,0,1]]

› Output: 7

💡 Note: All 7 possible subsets are valid since max distance is 2, which is ≤ 10.

Example 3 — Linear Chain

$ Input: n = 4, maxDistance = 4, roads = [[0,1,3],[1,2,3],[2,3,3]]

› Output: 8

💡 Note: Single branches and adjacent pairs are valid. Longer chains exceed maxDistance.

Constraints

2 ≤ n ≤ 15
1 ≤ maxDistance ≤ 10⁹
0 ≤ roads.length ≤ 1000
roads[i].length == 3
0 ≤ u_i, v_i ≤ n-1
u_i ≠ v_i
1 ≤ w_i ≤ 10⁹
All branches are initially reachable from each other

Visualization

Tap to expand

Understanding the Visualization

Input Graph

n=3 branches with roads and maxDistance=5

Compute Distances

Find shortest paths between all branch pairs

Check Subsets

Count subsets where max distance ≤ 5

Key Takeaway

🎯 Key Insight: Use bitmasks to enumerate all subsets and precompute distances for efficiency

Asked in

a Amazon 25 M Microsoft 18 G Google 12

The key insight is to use bit manipulation to enumerate all possible subsets of branches to keep open, then check if all pairwise distances in each subset are within the maxDistance constraint. Best approach precomputes all shortest paths using Floyd-Warshall once, then efficiently checks each subset. Time: O(n³ + 2ⁿ × n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Precomputed Distances	O(n³ + 2ⁿ × n²)	O(n²)	Precompute all-pairs shortest paths once, then efficiently check each subset
Brute Force with Enumeration	O(2ⁿ × n³)	O(n²)	Try all possible subsets of branches to keep open and check distance constraint

Optimized with Precomputed Distances — Algorithm Steps

Step 1: Build adjacency matrix from all roads
Step 2: Apply Floyd-Warshall once to get all shortest paths
Step 3: For each subset (bitmask), check precomputed distances
Step 4: Count subsets where all pairwise distances ≤ maxDistance

Visualization

Tap to expand

Step-by-Step Walkthrough

Floyd-Warshall

Compute all shortest paths once

Enumerate Subsets

Try each combination using bitmask

Distance Lookup

Check precomputed distances quickly

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define INF (INT_MAX / 2)

int solution(int n, int maxDistance, int roads[][3], int roadsSize) {
    // Build adjacency matrix and compute all-pairs shortest paths
    int** dist = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        dist[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            dist[i][j] = (i == j) ? 0 : INF;
        }
    }
    
    // Add roads
    for (int i = 0; i < roadsSize; i++) {
        int u = roads[i][0], v = roads[i][1], w = roads[i][2];
        if (dist[u][v] > w) dist[u][v] = w;
        if (dist[v][u] > w) dist[v][u] = w;
    }
    
    // Floyd-Warshall to compute all shortest paths
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }
    
    int count = 0;
    // Try all possible subsets (2^n)
    for (int mask = 1; mask < (1 << n); mask++) {
        // Get selected branches
        int selected[20], m = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                selected[m++] = i;
            }
        }
        
        // Single branch is always valid
        if (m == 1) {
            count++;
            continue;
        }
        
        // Check if all pairwise distances are within maxDistance
        int valid = 1;
        for (int i = 0; i < m && valid; i++) {
            for (int j = i + 1; j < m && valid; j++) {
                if (dist[selected[i]][selected[j]] > maxDistance) {
                    valid = 0;
                }
            }
        }
        
        if (valid) {
            count++;
        }
    }
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(dist[i]);
    }
    free(dist);
    
    return count;
}

int main() {
    int n, maxDistance;
    scanf("%d", &n);
    scanf("%d", &maxDistance);
    
    char line[1000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for roads array
    int roads[100][3];
    int roadsSize = 0;
    
    char* ptr = line + 1; // skip '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            roads[roadsSize][0] = strtol(ptr, &ptr, 10);
            ptr++; // skip ','
            roads[roadsSize][1] = strtol(ptr, &ptr, 10);
            ptr++; // skip ','
            roads[roadsSize][2] = strtol(ptr, &ptr, 10);
            roadsSize++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(n, maxDistance, roads, roadsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³ + 2ⁿ × n²)

O(n³) for Floyd-Warshall once, then O(n²) distance checks for each of 2^n subsets

⚠ Quadratic Growth

Space Complexity

O(n²)

Distance matrix storing all-pairs shortest paths

⚠ Quadratic Space

12.0K Views

Medium Frequency

~35 min Avg. Time

285 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Precomputed Distances — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler