leetcode

commit e696de5e2d3edfa215be03e899454536a52b3fa9
parent fd4f7a82f5ff55496da9bea2c5b4e7fce736a2a6
Author: Andrew Laack <andrew@laack.co>
Date:   Mon,  7 Jul 2025 12:16:44 -0500

Completed permutations

Diffstat:
A
permutations/permutationsV1.py
 | 
40
++++++++++++++++++++++++++++++++++++++++

1 file changed, 40 insertions(+), 0 deletions(-)
diff --git a/permutations/permutationsV1.py b/permutations/permutationsV1.py
@@ -0,0 +1,40 @@
+# Intuition:
+
+# Select 1 of n possible options
+# Remove said option from valid options list
+# Select next option with same process until len(str) == len(options)
+
+# Approach:
+
+# Naive:
+# Two loops where one specifies an option
+# and the other loops through the current list of selections
+# to ensure the current selection is not in there.
+# This is slow because it loops over each every time.
+
+# Another approach is similar except
+# removes the item from a copy of the list each time
+# while this can be faster, on average it won't be,
+# and will guarantee the same wctc.
+
+# Since all nums are unique, I think the first approach is actually the fastest.
+
+
+class Solution:
+    def permute(self, nums: List[int], current=[]) -> List[List[int]]:
+
+        if len(nums) == 0:
+            return [current]
+
+        results = []
+
+        for index, num in enumerate(nums):
+            cp_nums = nums.copy()
+            cv = cp_nums.pop(index)
+            cp_current = current.copy()
+            cp_current.append(cv)
+            result = self.permute(cp_nums, cp_current)
+            for res in result:
+                results.append(res)
+
+        return results