Repository: keon/algorithms
Pull request #306 (2018-06-05 04:27:34)

clean up backtrack and move tests to test_backtest
cleanin up.
just changed names and reformatted some functions.
moved tests from each files to tests/test_backtest file.
no new logic was added. Please take a look and review :)

coveralls: ## Pull Request Test Coverage Report for [Build 373](https://coveralls.io/builds/17320528)

* **214** of **228**   **(93.86%)**  changed or added relevant lines in **7** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage increased (+**0.2%**) to **91.854%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/backtrack/add_operators.py](https://coveralls.io/builds/17320528/source?filename=algorithms%2Fbacktrack%2Fadd_operators.py#L43) | 19 | 20 | 95.0%
| [algorithms/backtrack/pattern_match.py](https://coveralls.io/builds/17320528/source?filename=algorithms%2Fbacktrack%2Fpattern_match.py#L26) | 14 | 15 | 93.33%
| [tests/test_backtrack.py](https://coveralls.io/builds/17320528/source?filename=tests%2Ftest_backtrack.py#L83) | 84 | 87 | 96.55%
| [algorithms/backtrack/permute.py](https://coveralls.io/builds/17320528/source?filename=algorithms%2Fbacktrack%2Fpermute.py#L45) | 15 | 24 | 62.5%
<!-- | **Total:** | **214** | **228** | **93.86%** | -->


|  Totals | [![Coverage Status](https://coveralls.io/builds/17320528/badge)](https://coveralls.io/builds/17320528) |
| :-- | --: |
| Change from base [Build 371](https://coveralls.io/builds/17320361): |  0.2% |
| Covered Lines: | 3067 |
| Relevant Lines: | 3339 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/algorithms/backtrack/__init__.py b/algorithms/backtrack/__init__.py
new file mode 100644
index 0000000..f8cdab7
--- /dev/null
+++ b/algorithms/backtrack/__init__.py
@@ -0,0 +1,15 @@
+from .add_operators import *
+from .anagram import *
+from .array_sum_combinations import *
+from .combination_sum import *
+from .factor_combinations import *
+from .find_words import *
+from .generate_abbreviations import *
+from .generate_parenthesis import *
+from .letter_combination import *
+from .palindrome_partitioning import *
+from .pattern_match import *
+from .permute_unique import *
+from .permute import *
+from .subsets_unique import *
+from .subsets import *
diff --git a/algorithms/backtrack/add_operators.py b/algorithms/backtrack/add_operators.py
new file mode 100644
index 0000000..7a84739
--- /dev/null
+++ b/algorithms/backtrack/add_operators.py
@@ -0,0 +1,45 @@
+"""
+Given a string that contains only digits 0-9 and a target value,
+return all possibilities to add binary operators (not unary) +, -, or *
+between the digits so they prevuate to the target value.
+
+Examples:
+"123", 6 -> ["1+2+3", "1*2*3"]
+"232", 8 -> ["2*3+2", "2+3*2"]
+"105", 5 -> ["1*0+5","10-5"]
+"00", 0 -> ["0+0", "0-0", "0*0"]
+"3456237490", 9191 -> []
+"""
+
+
+def add_operators(num, target):
+    """
+    :type num: str
+    :type target: int
+    :rtype: List[str]
+    """
+
+    def dfs(res, path, num, target, pos, prev, multed):
+        if pos == len(num):
+            if target == prev:
+                res.append(path)
+            return
+        for i in range(pos, len(num)):
+            if i != pos and num[pos] == '0':  # all digits have to be used
+                break
+            cur = int(num[pos:i+1])
+            if pos == 0:
+                dfs(res, path + str(cur), num, target, i+1, cur, cur)
+            else:
+                dfs(res, path + "+" + str(cur), num, target,
+                    i+1, prev + cur, cur)
+                dfs(res, path + "-" + str(cur), num, target,
+                    i+1, prev - cur, -cur)
+                dfs(res, path + "*" + str(cur), num, target,
+                    i+1, prev - multed + multed * cur, multed * cur)
+
+    res = []
+    if not num:
+        return res
+    dfs(res, "", num, target, 0, 0, 0)
+    return res
diff --git a/algorithms/backtrack/anagram.py b/algorithms/backtrack/anagram.py
index 862140f..7c807cd 100644
--- a/algorithms/backtrack/anagram.py
+++ b/algorithms/backtrack/anagram.py
@@ -1,31 +1,3 @@
-import unittest
-
-def all_perms_iter(elements):
-    """
-        iterator: returns a perumation by each call. 
-    """
-    if len(elements) <=1:
-        yield elements
-    else:
-        for perm in all_perms_iter(elements[1:]):
-            for i in range(len(elements)):
-                yield perm[:i] + elements[0:1] + perm[i:]
-
-
-def all_perms(elements):
-    """
-        returns a list with the permuations.
-    """
-    if len(elements) <=1:
-        return elements
-    else:
-        tmp = []
-        for perm in all_perms(elements[1:]):
-            for i in range(len(elements)):
-                tmp.append(perm[:i] + elements[0:1] + perm[i:])
-        return tmp
-
-
 def anagram(s1, s2):
     c1 = [0] * 26
     c2 = [0] * 26
@@ -39,24 +11,3 @@ def anagram(s1, s2):
         c2[pos] = c2[pos] + 1
 
     return c1 == c2
-
-
-class TestSuite (unittest.TestCase):
-
-    def test_all_perms(self):
-        perms = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']
-        self.assertEqual(perms, all_perms("abc"))
-
-    def test_all_perms_iter(self):
-        it = all_perms_iter("abc")
-        perms = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']
-        for i in range(len(perms)):
-            self.assertEqual(perms[i], next(it))
-
-    def test_angram(self):
-        self.assertTrue(anagram('apple', 'pleap'))
-        self.assertFalse(anagram("apple", "cherry"))
-
-
-if __name__ == "__main__":
-    unittest.main()
diff --git a/algorithms/backtrack/array_sum_combinations.py b/algorithms/backtrack/array_sum_combinations.py
index b8dbc80..b152e4d 100644
--- a/algorithms/backtrack/array_sum_combinations.py
+++ b/algorithms/backtrack/array_sum_combinations.py
@@ -5,7 +5,7 @@ Print all those three-element combinations.
 /*
 A = [1, 2, 3, 3]
 B = [2, 3, 3, 4]
-C = [1, 2, 2, 2]
+C = [2, 3, 3, 4]
 target = 7
 */
 
@@ -16,79 +16,69 @@ Result:
 import itertools
 from functools import partial
 
-A = [1, 2, 3, 3]
-B = [2, 3, 3, 4]
-C = [1, 2, 2, 2]
-target = 7
-
-
-def construct_candidates(constructed_sofar):
-    global A, B, C
-    array = A
-    if 1 == len(constructed_sofar):
-        array = B
-    elif 2 == len(constructed_sofar):
-        array = C
-    return array
-
-
-def over(constructed_sofar):
-    global target
-    sum = 0
-    to_stop, reached_target = False, False
-    for elem in constructed_sofar:
-        sum += elem
-    if sum >= target or len(constructed_sofar) >= 3:
-        to_stop = True
-        if sum == target and 3 == len(constructed_sofar):
-            reached_target = True
-
-    return to_stop, reached_target
-
-
-def backtrack(constructed_sofar):
-    to_stop, reached_target = over(constructed_sofar)
-    if to_stop:
-        if reached_target:
-            print(constructed_sofar)
-        return
-    candidates = construct_candidates(constructed_sofar)
-    for candidate in candidates:
-        constructed_sofar.append(candidate)
-        backtrack(constructed_sofar[:])
-        constructed_sofar.pop()
-
-
-backtrack([])
-
-
-# Complexity: O(n(m+p))
-
-# 1. Sort all the arrays - a,b,c. - This will improve average time complexity.
-# 2. If c[i] < Sum, then look for Sum - c[i] in array a and b. When pair found,
-#    insert c[i], a[j] & b[k] into the result list. This can be done in O(n).
-# 3. Keep on doing the above procedure while going through complete c array.
-
-
-A = [1, 2, 3, 3]
-B = [2, 3, 3, 4]
-C = [1, 2, 2, 2]
-S = 7
-
-
-def check_sum(n, *nums):
-    if sum(x for x in nums) == n:
-        return (True, nums)
-    else:
-        return (False, nums)
-
-
-pro = itertools.product(A, B, C)
-func = partial(check_sum, S)
-sums = list(itertools.starmap(func, pro))
 
-res = set()
-for s in sums:
-    if s[0] is True and s[1] not in res:
-        res.add(s[1])
-print(res)
+def array_sum_combinations(A, B, C, target):
+
+    def over(constructed_sofar):
+        sum = 0
+        to_stop, reached_target = False, False
+        for elem in constructed_sofar:
+            sum += elem
+        if sum >= target or len(constructed_sofar) >= 3:
+            to_stop = True
+            if sum == target and 3 == len(constructed_sofar):
+                reached_target = True
+        return to_stop, reached_target
+
+    def construct_candidates(constructed_sofar):
+        array = A
+        if 1 == len(constructed_sofar):
+            array = B
+        elif 2 == len(constructed_sofar):
+            array = C
+        return array
+
+    def backtrack(constructed_sofar=[], res=[]):
+        to_stop, reached_target = over(constructed_sofar)
+        if to_stop:
+            if reached_target:
+                res.append(constructed_sofar)
+            return
+        candidates = construct_candidates(constructed_sofar)
+
+        for candidate in candidates:
+            constructed_sofar.append(candidate)
+            backtrack(constructed_sofar[:], res)
+            constructed_sofar.pop()
+
+    res = []
+    backtrack([], res)
+    return res
+
+
+def unique_array_sum_combinations(A, B, C, target):
+    """
+    1. Sort all the arrays - a,b,c. - This improves average time complexity.
+    2. If c[i] < Sum, then look for Sum - c[i] in array a and b.
+       When pair found, insert c[i], a[j] & b[k] into the result list.
+       This can be done in O(n).
+    3. Keep on doing the above procedure while going through complete c array.
+
+    Complexity: O(n(m+p))
+    """
+    def check_sum(n, *nums):
+        if sum(x for x in nums) == n:
+            return (True, nums)
+        else:
+            return (False, nums)
+
+    pro = itertools.product(A, B, C)
+    func = partial(check_sum, target)
+    sums = list(itertools.starmap(func, pro))
+
+    res = set()
+    for s in sums:
+        if s[0] is True and s[1] not in res:
+            res.add(s[1])
+
+    return list(res)
diff --git a/algorithms/backtrack/combination_sum.py b/algorithms/backtrack/combination_sum.py
index 8c67476..4d4dfb1 100644
--- a/algorithms/backtrack/combination_sum.py
+++ b/algorithms/backtrack/combination_sum.py
@@ -16,18 +16,18 @@ A solution set is:
 """
 
 
-def combination_sum(self, candidates, target):
+def combination_sum(candidates, target):
+
+    def dfs(nums, target, index, path, res):
+        if target < 0:
+            return  # backtracking
+        if target == 0:
+            res.append(path)
+            return
+        for i in range(index, len(nums)):
+            dfs(nums, target-nums[i], i, path+[nums[i]], res)
+
     res = []
     candidates.sort()
-    self.dfs(candidates, target, 0, [], res)
+    dfs(candidates, target, 0, [], res)
     return res
-
-
-def dfs(self, nums, target, index, path, res):
-    if target < 0:
-        return  # backtracking
-    if target == 0:
-        res.append(path)
-        return
-    for i in range(index, len(nums)):
-        self.dfs(nums, target-nums[i], i, path+[nums[i]], res)
diff --git a/algorithms/backtrack/expression_add_operators.py b/algorithms/backtrack/expression_add_operators.py
deleted file mode 100644
index f8f520f..0000000
--- a/algorithms/backtrack/expression_add_operators.py
+++ /dev/null
@@ -1,54 +0,0 @@
-"""
-Given a string that contains only digits 0-9 and a target value,
-return all possibilities to add binary operators (not unary) +, -, or *
-between the digits so they prevuate to the target value.
-
-Examples:
-"123", 6 -> ["1+2+3", "1*2*3"]
-"232", 8 -> ["2*3+2", "2+3*2"]
-"105", 5 -> ["1*0+5","10-5"]
-"00", 0 -> ["0+0", "0-0", "0*0"]
-"3456237490", 9191 -> []
-"""
-
-def add_operator(num, target):
-    """
-    :type num: str
-    :type target: int
-    :rtype: List[str]
-    """
-    res = []
-    if not num: return res
-    helper(res, "", num, target, 0, 0, 0)
-    return res
-
-
-def helper(res, path, num, target, pos, prev, multed):
-    if pos == len(num):
-        if target == prev:
-            res.append(path)
-        return
-    for i in range(pos, len(num)):
-        if i != pos and num[pos] == '0':  # all digits have to be used
-            break
-        cur = int(num[pos:i+1])
-        if pos == 0:
-            helper(res, path + str(cur), num, target, i+1, cur, cur)
-        else:
-            helper(res, path + "+" + str(cur), num, target, i+1, prev + cur, cur)
-            helper(res, path + "-" + str(cur), num, target, i+1, prev - cur, -cur)
-            helper(res, path + "*" + str(cur), num, target, i+1, prev - multed + multed * cur, multed * cur)
-
-
-# "123", 6 -> ["1+2+3", "1*2*3"]
-s = "123"
-target = 6
-print(add_operator(s, target))
-# "232", 8 -> ["2*3+2", "2+3*2"]
-s = "232"
-target = 8
-print(add_operator(s, target))
-
-s = "123045"
-target = 3
-print(add_operator(s, target))
diff --git a/algorithms/backtrack/factor_combinations.py b/algorithms/backtrack/factor_combinations.py
index d4de728..3240b05 100644
--- a/algorithms/backtrack/factor_combinations.py
+++ b/algorithms/backtrack/factor_combinations.py
@@ -3,7 +3,8 @@ Numbers can be regarded as product of its factors. For example,
 
 8 = 2 x 2 x 2;
   = 2 x 4.
-Write a function that takes an integer n and return all possible combinations of its factors.
+Write a function that takes an integer n
+and return all possible combinations of its factors.
 
 Note:
 You may assume that n is always positive.
@@ -49,7 +50,7 @@ def get_factors(n):
 
 
 # Recursive:
-def get_factors_recur(n):
+def recursive_get_factors(n):
 
     def factor(n, i, combi, combis):
         while i * i <= n:
diff --git a/algorithms/backtrack/find_words.py b/algorithms/backtrack/find_words.py
new file mode 100644
index 0000000..da6b634
--- /dev/null
+++ b/algorithms/backtrack/find_words.py
@@ -0,0 +1,73 @@
+'''
+Given a matrix of words and a list of words to search,
+return a list of words that exists in the board
+This is Word Search II on LeetCode
+
+board = [
+         ['o','a','a','n'],
+         ['e','t','a','e'],
+         ['i','h','k','r'],
+         ['i','f','l','v']
+         ]
+
+words = ["oath","pea","eat","rain"]
+'''
+
+
+def find_words(board, words):
+
+    def backtrack(board, i, j, trie, pre, used, result):
+        '''
+        backtrack tries to build each words from
+        the board and return all words found
+
+        @param: board, the passed in board of characters
+        @param: i, the row index
+        @param: j, the column index
+        @param: trie, a trie of the passed in words
+        @param: pre, a buffer of currently build string that differs
+                by recursion stack
+        @param: used, a replica of the board except in booleans
+                to state whether a character has been used
+        @param: result, the resulting set that contains all words found
+
+        @return: list of words found
+        '''
+
+        if '#' in trie:
+            result.add(pre)
+
+        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
+            return
+
+        if not used[i][j] and board[i][j] in trie:
+            used[i][j] = True
+            backtrack(board, i+1, j, trie[board[i][j]],
+                      pre+board[i][j], used, result)
+            backtrack(board, i, j+1, trie[board[i][j]],
+                      pre+board[i][j], used, result)
+            backtrack(board, i-1, j, trie[board[i][j]],
+                      pre+board[i][j], used, result)
+            backtrack(board, i, j-1, trie[board[i][j]],
+                      pre+board[i][j], used, result)
+            used[i][j] = False
+
+    # make a trie structure that is essentially dictionaries of dictionaries
+    # that map each character to a potential next character
+    trie = {}
+    for word in words:
+        curr_trie = trie
+        for char in word:
+            if char not in curr_trie:
+                curr_trie[char] = {}
+            curr_trie = curr_trie[char]
+        curr_trie['#'] = '#'
+
+    # result is a set of found words since we do not want repeats
+    result = set()
+    used = [[False]*len(board[0]) for _ in range(len(board))]
+
+    for i in range(len(board)):
+        for j in range(len(board[0])):
+            backtrack(board, i, j, trie, '', used, result)
+    return list(result)
diff --git a/algorithms/backtrack/general_solution.md b/algorithms/backtrack/general_solution.md
deleted file mode 100644
index 0c0ee0c..0000000
--- a/algorithms/backtrack/general_solution.md
+++ /dev/null
@@ -1,156 +0,0 @@
-This structure might apply to many other backtracking questions, but here I am just going to demonstrate Subsets, Permutations, and Combination Sum.
-
-# Subsets : https://leetcode.com/problems/subsets/
-
-public List<List<Integer>> subsets(int[] nums) {
-    List<List<Integer>> list = new ArrayList<>();
-    Arrays.sort(nums);
-    backtrack(list, new ArrayList<>(), nums, 0);
-    return list;
-}
-
-private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
-    list.add(new ArrayList<>(tempList));
-    for(int i = start; i < nums.length; i++){
-        tempList.add(nums[i]);
-        backtrack(list, tempList, nums, i + 1);
-        tempList.remove(tempList.size() - 1);
-    }
-}
-
-# Subsets II (contains duplicates) : https://leetcode.com/problems/subsets-ii/
-
-public List<List<Integer>> subsetsWithDup(int[] nums) {
-    List<List<Integer>> list = new ArrayList<>();
-    Arrays.sort(nums);
-    backtrack(list, new ArrayList<>(), nums, 0);
-    return list;
-}
-
-private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
-    list.add(new ArrayList<>(tempList));
-    for(int i = start; i < nums.length; i++){
-        if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
-        tempList.add(nums[i]);
-        backtrack(list, tempList, nums, i + 1);
-        tempList.remove(tempList.size() - 1);
-    }
-} 
-
-# Permutations : https://leetcode.com/problems/permutations/
-
-public List<List<Integer>> permute(int[] nums) {
-   List<List<Integer>> list = new ArrayList<>();
-   // Arrays.sort(nums); // not necessary
-   backtrack(list, new ArrayList<>(), nums);
-   return list;
-}
-
-private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
-   if(tempList.size() == nums.length){
-      list.add(new ArrayList<>(tempList));
-   } else{
-      for(int i = 0; i < nums.length; i++){ 
-         if(tempList.contains(nums[i])) continue; // element already exists, skip
-         tempList.add(nums[i]);
-         backtrack(list, tempList, nums);
-         tempList.remove(tempList.size() - 1);
-      }
-   }
-} 
-
-# Permutations II (contains duplicates) : https://leetcode.com/problems/permutations-ii/
-
-public List<List<Integer>> permuteUnique(int[] nums) {
-    List<List<Integer>> list = new ArrayList<>();
-    Arrays.sort(nums);
-    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
-    return list;
-}
-
-private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
-    if(tempList.size() == nums.length){
-        list.add(new ArrayList<>(tempList));
-    } else{
-        for(int i = 0; i < nums.length; i++){
-            if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
-            used[i] = true; 
-            tempList.add(nums[i]);
-            backtrack(list, tempList, nums, used);
-            used[i] = false; 
-            tempList.remove(tempList.size() - 1);
-        }
-    }
-}
-
-# Combination Sum : https://leetcode.com/problems/combination-sum/
-
-public List<List<Integer>> combinationSum(int[] nums, int target) {
-    List<List<Integer>> list = new ArrayList<>();
-    Arrays.sort(nums);
-    backtrack(list, new ArrayList<>(), nums, target, 0);
-    return list;
-}
-
-private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
-    if(remain < 0) return;
-    else if(remain == 0) list.add(new ArrayList<>(tempList));
-    else{ 
-        for(int i = start; i < nums.length; i++){
-            tempList.add(nums[i]);
-            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
-            tempList.remove(tempList.size() - 1);
-        }
-    }
-}
-# Combination Sum II (can't reuse same element) : https://leetcode.com/problems/combination-sum-ii/
-
-public List<List<Integer>> combinationSum2(int[] nums, int target) {
-    List<List<Integer>> list = new ArrayList<>();
-    Arrays.sort(nums);
-    backtrack(list, new ArrayList<>(), nums, target, 0);
-    return list;
-    
-}
-
-private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
-    if(remain < 0) return;
-    else if(remain == 0) list.add(new ArrayList<>(tempList));
-    else{
-        for(int i = start; i < nums.length; i++){
-            if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
-            tempList.add(nums[i]);
-            backtrack(list, tempList, nums, remain - nums[i], i + 1);
-            tempList.remove(tempList.size() - 1); 
-        }
-    }
-} 
-
-
-# Palindrome Partitioning : https://leetcode.com/problems/palindrome-partitioning/
-
-public List<List<String>> partition(String s) {
-   List<List<String>> list = new ArrayList<>();
-   backtrack(list, new ArrayList<>(), s, 0);
-   return list;
-}
-
-public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){
-   if(start == s.length())
-      list.add(new ArrayList<>(tempList));
-   else{
-      for(int i = start; i < s.length(); i++){
-         if(isPalindrome(s, start, i)){
-            tempList.add(s.substring(start, i + 1));
-            backtrack(list, tempList, s, i + 1);
-            tempList.remove(tempList.size() - 1);
-         }
-      }
-   }
-}
-
-public boolean isPalindrome(String s, int low, int high){
-   while(low < high)
-      if(s.charAt(low++) != s.charAt(high--)) return false;
-   return true;
-} 
diff --git a/algorithms/backtrack/generate_abbreviations.py b/algorithms/backtrack/generate_abbreviations.py
index 929c339..1329656 100644
--- a/algorithms/backtrack/generate_abbreviations.py
+++ b/algorithms/backtrack/generate_abbreviations.py
@@ -6,21 +6,21 @@ word => [1ord, w1rd, wo1d, w2d, 3d, w3 ... etc]
 
 
 def generate_abbreviations(word):
-    result = []
-    backtrack(result, word, 0, 0, "")
-    return result
 
+    def backtrack(result, word, pos, count, cur):
+        if pos == len(word):
+            if count > 0:
+                cur += str(count)
+            result.append(cur)
+            return
 
-def backtrack(result, word, pos, count, cur):
-    if pos == len(word):
-        if count > 0:
-            cur += str(count)
-        result.append(cur)
-        return
+        if count > 0:  # add the current word
+            backtrack(result, word, pos+1, 0, cur+str(count)+word[pos])
+        else:
+            backtrack(result, word, pos+1, 0, cur+word[pos])
+        # skip the current word
+        backtrack(result, word, pos+1, count+1, cur)
 
-    if count > 0:  # add the current word
-        backtrack(result, word, pos+1, 0, cur+str(count)+word[pos])
-    else:
-        backtrack(result, word, pos+1, 0, cur+word[pos])
-    # skip the current word
-    backtrack(result, word, pos+1, count+1, cur)
+    result = []
+    backtrack(result, word, 0, 0, "")
+    return result
diff --git a/algorithms/backtrack/generate_parenthesis.py b/algorithms/backtrack/generate_parenthesis.py
index 6dac22c..9b9eb8c 100644
--- a/algorithms/backtrack/generate_parenthesis.py
+++ b/algorithms/backtrack/generate_parenthesis.py
@@ -13,20 +13,17 @@ For example, given n = 3, a solution set is:
 ]
 """
 
-def gen_parenthesis(n:"int")->"List[str]":
+
+def generate_parenthesis(n):
+    def add_pair(res, s, left, right):
+        if left == 0 and right == 0:
+            res.append(s)
+            return
+        if right > 0:
+            add_pair(res, s+")", left, right-1)
+        if left > 0:
+            add_pair(res, s+"(", left-1, right+1)
+
     res = []
     add_pair(res, "", n, 0)
     return res
-
-def add_pair(res, s, left, right):
-    if left == 0 and right == 0:
-        res.append(s)
-        return
-    if right > 0:
-        add_pair(res, s+")", left, right-1)
-    if left > 0:
-        add_pair(res, s+"(", left-1, right+1)
-
-
-if __name__=="__main__":
-    print(gen_parenthesis(3))
diff --git a/algorithms/backtrack/letter_combination.py b/algorithms/backtrack/letter_combination.py
index f4a4c4e..8a2f8d1 100644
--- a/algorithms/backtrack/letter_combination.py
+++ b/algorithms/backtrack/letter_combination.py
@@ -7,7 +7,7 @@ Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 """
 
 
-def letter_combinations(digits:"str")->"List[str]":
+def letter_combinations(digits):
     if digits == "":
         return []
     kmaps = {
@@ -28,8 +28,3 @@ def letter_combinations(digits:"str")->"List[str]":
                 tmp.append(an + char)
         ans = tmp
     return ans
-
-
-if __name__ == "__main__":
-    digit_string = "23"
-    print(letter_combinations(digit_string))
diff --git a/algorithms/backtrack/palindrome_partitioning.py b/algorithms/backtrack/palindrome_partitioning.py
index 21500c1..052339d 100644
--- a/algorithms/backtrack/palindrome_partitioning.py
+++ b/algorithms/backtrack/palindrome_partitioning.py
@@ -1,8 +1,11 @@
 """ It looks like you need to be looking not for all palindromic substrings,
-but rather for all the ways you can divide the input string up into palindromic substrings.
-(There's always at least one way, since one-character substrings are always palindromes.)
+but rather for all the ways you can divide the input string
+up into palindromic substrings.
+(There's always at least one way,
+since one-character substrings are always palindromes.)
 """
 
+
 def palindromic_substrings(s):
     if not s:
         return [[]]
@@ -14,19 +17,26 @@ def palindromic_substrings(s):
                 results.append([sub] + rest)
     return results
 
-""" There's two loops.
-The outer loop checks each length of initial substring (in descending length order) to see 
-if it is a palindrome. If so, it recurses on the rest of the string and loops over the returned 
-values, adding the initial substring to each item before adding it to the results.
+
+"""
+There's two loops.
+The outer loop checks each length of initial substring
+(in descending length order) to see if it is a palindrome.
+If so, it recurses on the rest of the string and loops over the returned
+values, adding the initial substring to
+each item before adding it to the results.
 """
-# A slightly more Pythonic approach would be to make a recursive generator:
 
-def palindromic_substrings(s):
+
+def palindromic_substrings_iter(s):
+    """
+    A slightly more Pythonic approach with a recursive generator
+    """
     if not s:
         yield []
         return
     for i in range(len(s), 0, -1):
         sub = s[:i]
         if sub == sub[::-1]:
-            for rest in palindromic_substrings(s[i:]):
+            for rest in palindromic_substrings_iter(s[i:]):
                 yield [sub] + rest
diff --git a/algorithms/backtrack/pattern_match.py b/algorithms/backtrack/pattern_match.py
index 532dfb9..03a23a4 100644
--- a/algorithms/backtrack/pattern_match.py
+++ b/algorithms/backtrack/pattern_match.py
@@ -20,33 +20,23 @@ def pattern_match(pattern, string):
     :type string: str
     :rtype: bool
     """
-    return backtrack(pattern, string, {})
+    def backtrack(pattern, string, dic):
+
+        if len(pattern) == 0 and len(string) > 0:
+            return False
 
+        if len(pattern) == len(string) == 0:
+            return True
 
-def backtrack(pattern, string, dic):
-    print(dic)
-    if len(pattern) == 0 and len(string) > 0:
+        for end in range(1, len(string)-len(pattern)+2):
+            if pattern[0] not in dic and string[:end] not in dic.values():
+                dic[pattern[0]] = string[:end]
+                if backtrack(pattern[1:], string[end:], dic):
+                    return True
+                del dic[pattern[0]]
+            elif pattern[0] in dic and dic[pattern[0]] == string[:end]:
+                if backtrack(pattern[1:], string[end:], dic):
+                    return True
         return False
-    if len(pattern) == len(string) == 0:
-        return True
-    for end in range(1, len(string)-len(pattern)+2):
-        if pattern[0] not in dic and string[:end] not in dic.values():
-            dic[pattern[0]] = string[:end]
-            if backtrack(pattern[1:], string[end:], dic):
-                return True
-            del dic[pattern[0]]
-        elif pattern[0] in dic and dic[pattern[0]] == string[:end]:
-            if backtrack(pattern[1:], string[end:], dic):
-                return True
-    return False
-
-if __name__ == "__main__":
-    pattern1 = "abab"
-    string1 = "redblueredblue"
-    pattern2 = "aaaa"
-    string2 = "asdasdasdasd"
-    pattern3 = "aabb"
-    string3 = "xyzabcxzyabc"
-    print(pattern_match(pattern1, string1))
-    print(pattern_match(pattern2, string2))
-    print(pattern_match(pattern3, string3))
+
+    return backtrack(pattern, string, {})
diff --git a/algorithms/backtrack/permute.py b/algorithms/backtrack/permute.py
index 3975972..4ce4843 100644
--- a/algorithms/backtrack/permute.py
+++ b/algorithms/backtrack/permute.py
@@ -1,40 +1,54 @@
-# 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
+"""
+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(elements):
+    """
+        returns a list with the permuations.
+    """
+    if len(elements) <= 1:
+        return elements
+    else:
+        tmp = []
+        for perm in permute(elements[1:]):
+            for i in range(len(elements)):
+                tmp.append(perm[:i] + elements[0:1] + perm[i:])
+        return tmp
+
+
+def permute_iter(elements):
+    """
+        iterator: returns a perumation by each call.
+    """
+    if len(elements) <= 1:
+        yield elements
+    else:
+        for perm in permute_iter(elements[1:]):
+            for i in range(len(elements)):
+                yield perm[:i] + elements[0:1] + perm[i:]
+
 
 # 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))
+def permute_recursive(nums):
+    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]])
+
+    res = []
+    dfs(res, nums, [])
+    return res
diff --git a/algorithms/backtrack/permute_unique.py b/algorithms/backtrack/permute_unique.py
index 911d40c..3b82e2c 100644
--- a/algorithms/backtrack/permute_unique.py
+++ b/algorithms/backtrack/permute_unique.py
@@ -1,13 +1,16 @@
-# Given a collection of numbers that might contain duplicates,
-# return all possible unique permutations.
+"""
+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]
+]
+"""
 
-# For example,
-# [1,1,2] have the following unique permutations:
-# [
-  # [1,1,2],
-  # [1,2,1],
-  # [2,1,1]
-# ]
 
 def permute_unique(nums):
     perms = [[]]
@@ -16,9 +19,7 @@ def permute_unique(nums):
         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
+                if i < len(l) and l[i] == n:
+                    break  # handles duplication
         perms = new_perms
     return perms
-
-
diff --git a/algorithms/backtrack/subsets.py b/algorithms/backtrack/subsets.py
index a1f63b0..a11c3c9 100644
--- a/algorithms/backtrack/subsets.py
+++ b/algorithms/backtrack/subsets.py
@@ -1,59 +1,64 @@
-# Given a set of distinct integers, nums, return all possible subsets.
+"""
+Given a set of distinct integers, nums, return all possible subsets.
 
-# Note: The solution set must not contain duplicate subsets.
+Note: The solution set must not contain duplicate subsets.
 
-# For example,
-# If nums = [1,2,3], a solution is:
+For example,
+If nums = [1,2,3], a solution is:
 
-# [
-  # [3],
-  # [1],
-  # [2],
-  # [1,2,3],
-  # [1,3],
-  # [2,3],
-  # [1,2],
-  # []
-# ]
-
-
-# O(2**n)
+[
+  [3],
+  [1],
+  [2],
+  [1,2,3],
+  [1,3],
+  [2,3],
+  [1,2],
+  []
+]
+"""
 
 
 def subsets(nums):
+    """
+    O(2**n)
+    """
+    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)
+
     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
 
-# 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)
+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)
+"""
 
 
 # Iteratively
-def subsets2(self, nums):
+def subsets_v2(self, nums):
     res = [[]]
     for num in sorted(nums):
         res += [item+[num] for item in res]
     return res
 
-test = [1,2,3]
+
+test = [1, 2, 3]
 print(test)
 print(subsets(test))
diff --git a/algorithms/backtrack/subsets_unique.py b/algorithms/backtrack/subsets_unique.py
index fac0cb0..a99f25c 100644
--- a/algorithms/backtrack/subsets_unique.py
+++ b/algorithms/backtrack/subsets_unique.py
@@ -1,38 +1,42 @@
-# Given a collection of integers that might contain duplicates, nums,
-# return all possible subsets.
+"""
+Given a collection of integers that might contain duplicates, nums,
+return all possible subsets.
 
-# Note: The solution set must not contain duplicate subsets.
+Note: The solution set must not contain duplicate subsets.
 
-# For example,
-# If nums = [1,2,2], a solution is:
+For example,
+If nums = [1,2,2], a solution is:
+
+[
+  [2],
+  [1],
+  [1,2,2],
+  [2,2],
+  [1,2],
+  []
+]
+"""
 
-# [
-  # [2],
-  # [1],
-  # [1,2,2],
-  # [2,2],
-  # [1,2],
-  # []
-# ]
 
 def subsets_unique(nums):
+
+    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)
+
     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]
+test = [1, 2, 2]
 print(test)
 print(subsets_unique(test))
diff --git a/algorithms/backtrack/word_search.py b/algorithms/backtrack/word_search.py
deleted file mode 100644
index 989e5b2..0000000
--- a/algorithms/backtrack/word_search.py
+++ /dev/null
@@ -1,111 +0,0 @@
-import unittest
-'''
-Given a matrix of words and a list of words to search, return a list of words that exists in the board
-This is Word Search II on LeetCode
-
-board = [
-         ['o','a','a','n'],
-         ['e','t','a','e'],
-         ['i','h','k','r'],
-         ['i','f','l','v']
-         ]
-
-words = ["oath","pea","eat","rain"]
-
-'''
-
-def find_words(board, words):
-    # make a trie structure that is essentially dictionaries of dictionaries that map each character to a potential next character
-    trie = {}
-    for word in words:
-        curr_trie = trie
-        for char in word:
-            if char not in curr_trie:
-                curr_trie[char] = {}
-            curr_trie = curr_trie[char]
-        curr_trie['#'] = '#'
-
-    # result is a set of found words since we do not want repeats
-    result = set()
-    used = [[False]*len(board[0]) for _ in range(len(board))]
-    
-    for i in range(len(board)):
-        for j in range(len(board[0])):
-            backtrack(board, i, j, trie, '', used, result)
-    return list(result)
-
-'''
-backtrack tries to build each words from the board and return all words found
-@param: board, the passed in board of characters
-@param: i, the row index
-@param: j, the column index
-@param: trie, a trie of the passed in words
-@param: pre, a buffer of currently build string that differs by recursion stack
-@param: used, a replica of the board except in booleans to state whether a character has been used
-@param: result, the resulting set that contains all words found
-
-@return: list of words found
-'''
-
-def backtrack(board, i, j, trie, pre, used, result):
-    if '#' in trie:
-        result.add(pre)
-    
-    if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
-        return
-    
-    if not used[i][j] and board[i][j] in trie:
-        used[i][j]=True
-        backtrack(board,i+1,j,trie[board[i][j]],pre+board[i][j], used, result)
-        backtrack(board,i,j+1,trie[board[i][j]],pre+board[i][j], used, result)
-        backtrack(board,i-1,j,trie[board[i][j]],pre+board[i][j], used, result)
-        backtrack(board,i,j-1,trie[board[i][j]],pre+board[i][j], used, result)
-        used[i][j]=False
-
-class MyTests(unittest.TestCase):
-    def test_normal(self):
-        board = [
-         ['o','a','a','n'],
-         ['e','t','a','e'],
-         ['i','h','k','r'],
-         ['i','f','l','v']
-         ]
-
-        words = ["oath","pea","eat","rain"]  
-        self.assertEqual(find_words(board, words), ['oath', 'eat'])
-
-    def test_none(self):
-        board = [
-         ['o','a','a','n'],
-         ['e','t','a','e'],
-         ['i','h','k','r'],
-         ['i','f','l','v']
-         ]
-
-        words = ["chicken", "nugget", "hello", "world"]  
-        self.assertEqual(find_words(board, words), [])
-
-    def test_empty(self):
-        board = []
-        words = []
-        self.assertEqual(find_words(board, words), [])
-
-    def test_uneven(self):
-        board = [
-         ['o','a','a','n'],
-         ['e','t','a','e']
-        ]
-        words = ["oath","pea","eat","rain"]  
-        self.assertEqual(find_words(board, words), ['eat'])
-
-    def test_repeat(self):
-        board = [
-        ['a','a','a'],
-        ['a','a','a'],
-        ['a','a','a']
-        ]
-        words = ["a", "aa", "aaa", "aaaa", "aaaaa"]
-        self.assertTrue(len(find_words(board, words))==5)
-
-if __name__=="__main__":
-    unittest.main()


Test patch:
diff --git a/tests/test_backtrack.py b/tests/test_backtrack.py
new file mode 100644
index 0000000..2e01d59
--- /dev/null
+++ b/tests/test_backtrack.py
@@ -0,0 +1,170 @@
+from algorithms.backtrack import (
+    add_operators,
+    permute,
+    permute_iter,
+    anagram,
+    array_sum_combinations,
+    unique_array_sum_combinations,
+    combination_sum,
+    find_words,
+    pattern_match,
+)
+
+import unittest
+
+
+class TestAddOperator(unittest.TestCase):
+    def test_add_operators(self):
+        # "123", 6 -> ["1+2+3", "1*2*3"]
+        s = "123"
+        target = 6
+        self.assertEqual(add_operators(s, target), ["1+2+3", "1*2*3"])
+        # "232", 8 -> ["2*3+2", "2+3*2"]
+        s = "232"
+        target = 8
+        self.assertEqual(add_operators(s, target), ["2+3*2", "2*3+2"])
+
+        s = "123045"
+        target = 3
+        answer = ['1+2+3*0*4*5',
+                  '1+2+3*0*45',
+                  '1+2-3*0*4*5',
+                  '1+2-3*0*45',
+                  '1-2+3+0-4+5',
+                  '1-2+3-0-4+5',
+                  '1*2+3*0-4+5',
+                  '1*2-3*0-4+5',
+                  '1*23+0-4*5',
+                  '1*23-0-4*5',
+                  '12+3*0-4-5',
+                  '12-3*0-4-5']
+        self.assertEqual(add_operators(s, target), answer)
+
+
+class TestPermuteAndAnagram(unittest.TestCase):
+
+    def test_permute(self):
+        perms = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']
+        self.assertEqual(perms, permute("abc"))
+
+    def test_permute_iter(self):
+        it = permute_iter("abc")
+        perms = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']
+        for i in range(len(perms)):
+            self.assertEqual(perms[i], next(it))
+
+    def test_angram(self):
+        self.assertTrue(anagram('apple', 'pleap'))
+        self.assertFalse(anagram("apple", "cherry"))
+
+
+class TestArrayCombinationSum(unittest.TestCase):
+
+    def test_array_sum_combinations(self):
+        A = [1, 2, 3, 3]
+        B = [2, 3, 3, 4]
+        C = [2, 3, 3, 4]
+        target = 7
+        answer = [[1, 2, 4], [1, 3, 3], [1, 3, 3], [1, 3, 3],
+                  [1, 3, 3], [1, 4, 2], [2, 2, 3], [2, 2, 3],
+                  [2, 3, 2], [2, 3, 2], [3, 2, 2], [3, 2, 2]]
+        self.assertEqual(array_sum_combinations(A, B, C, target), answer)
+
+    def test_unique_array_sum_combinations(self):
+        A = [1, 2, 3, 3]
+        B = [2, 3, 3, 4]
+        C = [2, 3, 3, 4]
+        target = 7
+        answer = [(2, 3, 2), (3, 2, 2), (1, 2, 4),
+                  (1, 4, 2), (2, 2, 3), (1, 3, 3)]
+        self.assertEqual(unique_array_sum_combinations(A, B, C, target), answer)
+
+
+class TestCombinationSum(unittest.TestCase):
+
+    def check_sum(self, nums, target):
+        if sum(nums) == target:
+            return (True, nums)
+        else:
+            return (False, nums)
+
+    def test_combination_sum(self):
+        candidates1 = [2, 3, 6, 7]
+        target1 = 7
+        answer1 = [
+            [2, 2, 3],
+            [7]
+        ]
+        self.assertEqual(combination_sum(candidates1, target1), answer1)
+
+        candidates2 = [2, 3, 5]
+        target2 = 8
+        answer2 = [
+            [2, 2, 2, 2],
+            [2, 3, 3],
+            [3, 5]
+        ]
+        self.assertEqual(combination_sum(candidates2, target2), answer2)
+
+
+class TestFindWords(unittest.TestCase):
+
+    def test_normal(self):
+        board = [
+             ['o', 'a', 'a', 'n'],
+             ['e', 't', 'a', 'e'],
+             ['i', 'h', 'k', 'r'],
+             ['i', 'f', 'l', 'v']
+        ]
+
+        words = ["oath", "pea", "eat", "rain"]
+        self.assertEqual(find_words(board, words).sort(),
+                         ['oath', 'eat'].sort())
+
+    def test_none(self):
+        board = [
+             ['o', 'a', 'a', 'n'],
+             ['e', 't', 'a', 'e'],
+             ['i', 'h', 'k', 'r'],
+             ['i', 'f', 'l', 'v']
+        ]
+
+        words = ["chicken", "nugget", "hello", "world"]
+        self.assertEqual(find_words(board, words), [])
+
+    def test_empty(self):
+        board = []
+        words = []
+        self.assertEqual(find_words(board, words), [])
+
+    def test_uneven(self):
+        board = [
+            ['o', 'a', 'a', 'n'],
+            ['e', 't', 'a', 'e']
+        ]
+        words = ["oath", "pea", "eat", "rain"]
+        self.assertEqual(find_words(board, words), ['eat'])
+
+    def test_repeat(self):
+        board = [
+            ['a', 'a', 'a'],
+            ['a', 'a', 'a'],
+            ['a', 'a', 'a']
+        ]
+        words = ["a", "aa", "aaa", "aaaa", "aaaaa"]
+        self.assertTrue(len(find_words(board, words)) == 5)
+
+
+class TestPatternMatch(unittest.TestCase):
+
+    def test_pattern_match(self):
+        pattern1 = "abab"
+        string1 = "redblueredblue"
+        pattern2 = "aaaa"
+        string2 = "asdasdasdasd"
+        pattern3 = "aabb"
+        string3 = "xyzabcxzyabc"
+
+        self.assertTrue(pattern_match(pattern1, string1))
+        self.assertTrue(pattern_match(pattern2, string2))
+        self.assertFalse(pattern_match(pattern3, string3))