algorithms

commit 9718ac04be30e364279b5b84b84aecc9cdcfd4f4
parent 37dcccf8eb7126af495e0e82593df5cae7333327
Author: Andrew Laack <andrew@laack.co>
Date:   Fri, 21 Aug 2026 11:57:36 -0500

MST in python and subsets in c++

Diffstat:
A
min-cost-to-connect-all-points/min-cost-to-connect-all-points.py
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
A
subsets/subsets.cpp
 | 
24
++++++++++++++++++++++++

2 files changed, 67 insertions(+), 0 deletions(-)
diff --git a/min-cost-to-connect-all-points/min-cost-to-connect-all-points.py b/min-cost-to-connect-all-points/min-cost-to-connect-all-points.py
@@ -0,0 +1,43 @@
+# Uses minimum spanning tree, induced using prim's algorith
+# Uses an adjacency list to represent edges and costs
+
+def man_dist(p_1, p_2):
+    return abs(p_1[0] - p_2[0]) + abs(p_1[1] - p_2[1])
+
+class Solution:
+    def minCostConnectPoints(self, points: List[List[int]]) -> int:
+        
+        edges = {}
+
+        for p_1 in range(len(points) - 1):
+            for p_2 in range(p_1 + 1, len(points)):
+                if not p_1 in edges:
+                    edges[p_1] = {}
+                if not p_2 in edges:
+                    edges[p_2] = {}
+                
+                dst = man_dist(points[p_1], points[p_2])
+                edges[p_1][p_2] = dst
+                edges[p_2][p_1] = dst
+        
+
+        # starting at point 0.
+        used = set()
+        used.add(0)
+        dist = 0
+
+        while len(used) != len(points):
+            
+            best_dist = -1
+            best_edge = -1
+
+            for i in used:
+                for edge in edges[i]:
+                    if not edge in used and (best_dist == -1 or edges[i][edge] < best_dist):
+                        best_edge = edge
+                        best_dist = edges[i][edge]
+            
+            used.add(best_edge)
+            dist += best_dist
+
+        return dist
diff --git a/subsets/subsets.cpp b/subsets/subsets.cpp
@@ -0,0 +1,24 @@
+class Solution {
+public:
+
+    // IDEA:
+    // To construct all possible subsets we may either include an element or not.
+    // Since sets are unique (and the problem says as much), we don't need a de-dupe pass.
+    
+    vector<vector<int>> recurse(vector<int> base, vector<int>& nums, int count) {
+        if (count >= nums.size()){
+            return vector<vector<int>> {base};
+        }
+
+        auto exclude = recurse(base, nums, count + 1);
+        base.push_back(nums[count]);
+        auto include = recurse(base, nums, count + 1);
+
+        exclude.insert(exclude.end(), include.begin(), include.end());
+        return exclude;
+    }
+
+    vector<vector<int>> subsets(vector<int>& nums) {
+        return recurse(vector<int>{}, nums, 0);
+    }
+};