minor shits

keon · keon · commit 3ce776a58388 · 2016-12-24T22:12:38.000-05:00
diff --git a/backtrack/anagram.py b/backtrack/anagram.py
diff --git a/backtrack/combination_sum.py b/backtrack/combination_sum.py
diff --git a/backtrack/palindrome_partitioning.py b/backtrack/palindrome_partitioning.py
diff --git a/backtrack/permute.py b/backtrack/permute.py
@@ -0,0 +1,40 @@
+# Given a collection of distinct numbers, return all possible permutations.
+
+# For example,
+# [1,2,3] have the following permutations:
+# [
+  # [1,2,3],
+  # [1,3,2],
+  # [2,1,3],
+  # [2,3,1],
+  # [3,1,2],
+  # [3,2,1]
+# ]
+
+def permute(nums):
+    perms = [[]]
+    for n in nums:
+        new_perms = []
+        for perm in perms:
+            for i in range(len(perm)+1):
+                new_perms.append(perm[:i] + [n] + perm[i:])   ###insert n
+                print(i, perm[:i], [n], perm[i:], ">>>>", new_perms)
+        perms = new_perms
+    return perms
+
+# DFS Version
+# def permute(nums):
+    # res = []
+    # dfs(res, nums, [])
+    # return res
+
+# def dfs(res, nums, path):
+    # if not nums:
+        # res.append(path)
+    # for i in range(len(nums)):
+        # print(nums[:i]+nums[i+1:])
+        # dfs(res, nums[:i]+nums[i+1:], path+[nums[i]])
+
+test = [1,2,3]
+print(test)
+print(permute(test))
diff --git a/backtrack/permute_unique.py b/backtrack/permute_unique.py
@@ -0,0 +1,24 @@
+# Given a collection of numbers that might contain duplicates,
+# return all possible unique permutations.
+
+# For example,
+# [1,1,2] have the following unique permutations:
+# [
+  # [1,1,2],
+  # [1,2,1],
+  # [2,1,1]
+# ]
+
+def permute_unique(nums):
+    perms = [[]]
+    for n in nums:
+        new_perms = []
+        for l in perms:
+            for i in range(len(l)+1):
+                new_perms.append(l[:i]+[n]+l[i:])
+                if i<len(l) and l[i]==n:
+                    break #handles duplication
+        perms = new_perms
+    return perms
+
+
diff --git a/backtrack/subsets.py b/backtrack/subsets.py
@@ -0,0 +1,49 @@
+# Given a set of distinct integers, nums, return all possible subsets.
+
+# Note: The solution set must not contain duplicate subsets.
+
+# For example,
+# If nums = [1,2,3], a solution is:
+
+# [
+  # [3],
+  # [1],
+  # [2],
+  # [1,2,3],
+  # [1,3],
+  # [2,3],
+  # [1,2],
+  # []
+# ]
+
+
+def subsets(nums):
+    res = []
+    backtrack(res, nums, [], 0)
+    return res
+
+def backtrack(res, nums, stack, pos):
+    if pos == len(nums):
+        res.append(list(stack))
+    else:
+        # take nums[pos]
+        stack.append(nums[pos])
+        backtrack(res, nums, stack, pos+1)
+        stack.pop()
+        # dont take nums[pos]
+        backtrack(res, nums, stack, pos+1)
+
+
+# simplified backtrack
+
+# def backtrack(res, nums, cur, pos):
+    # if pos >= len(nums):
+        # res.append(cur)
+    # else:
+        # backtrack(res, nums, cur+[nums[pos]], pos+1)
+        # backtrack(res, nums, cur, pos+1)
+
+
+test = [1,2,3]
+print(test)
+print(subsets(test))
diff --git a/backtrack/subsets_unique.py b/backtrack/subsets_unique.py
@@ -0,0 +1,38 @@
+# Given a collection of integers that might contain duplicates, nums,
+# return all possible subsets.
+
+# Note: The solution set must not contain duplicate subsets.
+
+# For example,
+# If nums = [1,2,2], a solution is:
+
+# [
+  # [2],
+  # [1],
+  # [1,2,2],
+  # [2,2],
+  # [1,2],
+  # []
+# ]
+
+def subsets_unique(nums):
+    res = set()
+    backtrack(res, nums, [], 0)
+    return list(res)
+
+def backtrack(res, nums, stack, pos):
+    if pos == len(nums):
+        res.add(tuple(stack))
+    else:
+        # take
+        stack.append(nums[pos])
+        backtrack(res, nums, stack, pos+1)
+        stack.pop()
+
+        # don't take
+        backtrack(res, nums, stack, pos+1)
+
+
+test = [1,2,2]
+print(test)
+print(subsets_unique(test))
diff --git a/search/binary_search.py b/search/binary_search.py
@@ -1,11 +1,9 @@
+
+
 def binary_search(array, query):
     lo, hi = 0, len(array) - 1
     while lo <= hi:
-        print("--------")
         mid = lo + (hi - lo) // 2
-        print("lo: ", lo)
-        print("hi: ", hi)
-        print("mid: ", mid)
         val = array[mid]
         if val == query:
             return mid
diff --git a/sorting/merge_sort.py b/sorting/merge_sort.py
@@ -2,13 +2,12 @@ def merge_sort(arr):
     """ Merge Sort
         Complexity: O(n log(n))
     """
-    size = len(arr)
-    half = size/2
     # Our recursive base case
-    if size <= 1:
+    if len(arr)<= 1:
         return arr
+    mid = len(arr)/2
     # Perform merge_sort recursively on both halves
-    left, right = merge_sort(arr[half:]), merge_sort(arr[:half])
+    left, right = merge_sort(arr[mid:]), merge_sort(arr[:mid])
 
     # Merge each side together
     return merge(left, right)
diff --git a/string/reverse_words.py b/string/reverse_words.py
@@ -11,7 +11,7 @@ def reverse_words(string):
     reverse(arr, 0, n-1)
 
     start = None
-    for i in range(n-1):
+    for i in range(n):
         if arr[i] == " ":
            if start:
                 reverse(arr, start, i-1)
