[C++/Python] Bitmask try all subset of cities - Clean & Concise - O(2^n * n)
Solution 1: Bitmask + Floyd Warshall\n- Using Floyd-Warshall algorithm to calculate minimum distance between any node to any other node.\n- Since n <= 15, there
**Solution 1: Bitmask + Floyd Warshall**\n- Using Floyd-Warshall algorithm to calculate minimum distance between any node to any other node.\n- Since `n <= 15`, there is a maximum `2^15` subset of cities numbered from `1` to `n`.\n- For each of subset of cities:\n\t- Our subset forms a subtree if and only if `number of edges = number of cities - 1`\n\t- Iterate all pair of cities to calculate `number of edges `, `number of cities`, `maximum distance between any 2 cities`\n\nComplexity\n- Time: `O(2^n * n^2)`\n- Space: `O(n^2)`\n\n<iframe src="https://leetcode.com/playground/fr3jcKi9/shared" frameBorder="0" width="100%" height="660"></iframe>\n\n**Solution 2: Bitmask + BFS every cities**\n- Since `n <= 15`, there is a maximum `2^15` subset of cities numbered from `1` to `n`.\n- For each of subset of cities, we calculate the **maximum distance** between any two cities in our subset.\n\t- For each `city` in our subset:\n\t\t- Using `bfs()` or `dsf()` to calculate distance between `city` to other cities in subset.\n\t\t- If `citiy` can\'t reach to any other cities then subset form an **invalid subtree.**\n\t- Return distance of 2 cities with maxium distance.\n\nComplexity\n- Time: `O(2^n * n^2)`\n- Space: `O(n^2)`\n\n<iframe src="https://leetcode.com/playground/PLUBYjTt/shared" frameBorder="0" width="100%" height="650"></iframe>\n\n**Solution 3: Bitmask + Diamter of the tree (BFS 2 times)**\n- Since `n <= 15`, there is a maximum `2^15` subset of cities numbered from `1` to `n`.\n- For each of subset, we calculate the **maximum distance** between any two cities in our subset. \n- **Maximum distance** between any two cities in our subset (subset must be a subtree) is the **diameter** of the tree. Can reference: https://leetcode.com/problems/tree-diameter/\n\nComplexity\n- Time: `O(2^n * n)`\n- Space: `O(n^2)`\n\n<iframe src="https://leetcode.com/playground/beLfGngX/shared" frameBorder="0" width="100%" height="800"></iframe>\n\nCredit [@siranjoy](https://leetcode.com/siranjoy/) for reminding me this approach.
[]