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: 7

💡 Note: Valid subsets: {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}. After Floyd-Warshall, dist[1][2] = 3 (via path 1→0→2), so all distances are ≤ 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: 7

💡 Note: Single branches and adjacent pairs are valid: {0}, {1}, {2}, {3}, {0,1}, {1,2}, {2,3}. Longer chains exceed maxDistance of 4.

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

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

✓ Brute Force with Enumeration

⏱️ Time: O(2ⁿ × n³) Space: O(n²)

Generate all possible subsets of branches using bit manipulation. For each subset, build the induced subgraph and check if all pairwise distances are within maxDistance using Floyd-Warshall algorithm.

Optimized with Precomputed Distances

⏱️ Time: O(n³ + 2ⁿ × n²) Space: O(n²)

First compute all-pairs shortest paths using Floyd-Warshall on the entire graph. Then for each subset, simply look up precomputed distances instead of recalculating them.

Brute Force with Enumeration — Algorithm Steps

Step 1: Enumerate all 2^n possible subsets of branches using bitmasks
Step 2: For each subset, build adjacency matrix with only selected branches
Step 3: Apply Floyd-Warshall to find shortest paths between all pairs
Step 4: Check if all distances are ≤ maxDistance, count valid subsets

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Use bitmask to try all 2^n combinations

Floyd-Warshall

Calculate shortest paths for each subset

Check Constraint

Verify all distances ≤ maxDistance

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
    int** adj = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        adj[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            adj[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 (adj[u][v] > w) adj[u][v] = w;
        if (adj[v][u] > w) adj[v][u] = w;
    }
    
    // Apply Floyd-Warshall to the full graph first
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (adj[i][k] != INF && adj[k][j] != INF) {
                    if (adj[i][k] + adj[k][j] < adj[i][j]) {
                        adj[i][j] = adj[i][k] + adj[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;
            }
        }
        
        // Check if all distances between selected branches are within maxDistance
        int valid = 1;
        for (int i = 0; i < m && valid; i++) {
            for (int j = 0; j < m && valid; j++) {
                if (adj[selected[i]][selected[j]] > maxDistance) {
                    valid = 0;
                }
            }
        }
        
        if (valid) {
            count++;
        }
    }
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(adj[i]);
    }
    free(adj);
    
    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;
    
    if (strcmp(line, "[]\n") != 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(2ⁿ × n³)

2^n subsets, each requiring O(n³) Floyd-Warshall algorithm

⚠ Quadratic Growth

Space Complexity

O(n²)

Distance matrix for Floyd-Warshall algorithm

⚠ 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

Number of Possible Sets of Closing Branches - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler