Skip to content

Commit f6aa8d6

Browse files
keongoswami-rahul
keon
authored and
goswami-rahul
committed
clean up backtrack and move tests to test_backtest (keon#306)
* clean up backtrack and add tests * fix typos in backtrack
1 parent 36c1af4 commit f6aa8d6

20 files changed

Lines changed: 585 additions & 645 deletions

‎algorithms/backtrack/__init__.py‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
from .add_operators import *
2+
from .anagram import *
3+
from .array_sum_combinations import *
4+
from .combination_sum import *
5+
from .factor_combinations import *
6+
from .find_words import *
7+
from .generate_abbreviations import *
8+
from .generate_parenthesis import *
9+
from .letter_combination import *
10+
from .palindrome_partitioning import *
11+
from .pattern_match import *
12+
from .permute_unique import *
13+
from .permute import *
14+
from .subsets_unique import *
15+
from .subsets import *

‎algorithms/backtrack/add_operators.py‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
"""
2+
Given a string that contains only digits 0-9 and a target value,
3+
return all possibilities to add binary operators (not unary) +, -, or *
4+
between the digits so they prevuate to the target value.
5+
6+
Examples:
7+
"123", 6 -> ["1+2+3", "1*2*3"]
8+
"232", 8 -> ["2*3+2", "2+3*2"]
9+
"105", 5 -> ["1*0+5","10-5"]
10+
"00", 0 -> ["0+0", "0-0", "0*0"]
11+
"3456237490", 9191 -> []
12+
"""
13+
14+
15+
def add_operators(num, target):
16+
"""
17+
:type num: str
18+
:type target: int
19+
:rtype: List[str]
20+
"""
21+
22+
def dfs(res, path, num, target, pos, prev, multed):
23+
if pos == len(num):
24+
if target == prev:
25+
res.append(path)
26+
return
27+
for i in range(pos, len(num)):
28+
if i != pos and num[pos] == '0': # all digits have to be used
29+
break
30+
cur = int(num[pos:i+1])
31+
if pos == 0:
32+
dfs(res, path + str(cur), num, target, i+1, cur, cur)
33+
else:
34+
dfs(res, path + "+" + str(cur), num, target,
35+
i+1, prev + cur, cur)
36+
dfs(res, path + "-" + str(cur), num, target,
37+
i+1, prev - cur, -cur)
38+
dfs(res, path + "*" + str(cur), num, target,
39+
i+1, prev - multed + multed * cur, multed * cur)
40+
41+
res = []
42+
if not num:
43+
return res
44+
dfs(res, "", num, target, 0, 0, 0)
45+
return res

‎algorithms/backtrack/anagram.py‎

Lines changed: 0 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -1,31 +1,3 @@
1-
import unittest
2-
3-
def all_perms_iter(elements):
4-
"""
5-
iterator: returns a perumation by each call.
6-
"""
7-
if len(elements) <=1:
8-
yield elements
9-
else:
10-
for perm in all_perms_iter(elements[1:]):
11-
for i in range(len(elements)):
12-
yield perm[:i] + elements[0:1] + perm[i:]
13-
14-
15-
def all_perms(elements):
16-
"""
17-
returns a list with the permuations.
18-
"""
19-
if len(elements) <=1:
20-
return elements
21-
else:
22-
tmp = []
23-
for perm in all_perms(elements[1:]):
24-
for i in range(len(elements)):
25-
tmp.append(perm[:i] + elements[0:1] + perm[i:])
26-
return tmp
27-
28-
291
def anagram(s1, s2):
302
c1 = [0] * 26
313
c2 = [0] * 26
@@ -39,24 +11,3 @@ def anagram(s1, s2):
3911
c2[pos] = c2[pos] + 1
4012

4113
return c1 == c2
42-
43-
44-
class TestSuite (unittest.TestCase):
45-
46-
def test_all_perms(self):
47-
perms = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']
48-
self.assertEqual(perms, all_perms("abc"))
49-
50-
def test_all_perms_iter(self):
51-
it = all_perms_iter("abc")
52-
perms = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']
53-
for i in range(len(perms)):
54-
self.assertEqual(perms[i], next(it))
55-
56-
def test_angram(self):
57-
self.assertTrue(anagram('apple', 'pleap'))
58-
self.assertFalse(anagram("apple", "cherry"))
59-
60-
61-
if __name__ == "__main__":
62-
unittest.main()

‎algorithms/backtrack/array_sum_combinations.py‎

Lines changed: 66 additions & 76 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
/*
66
A = [1, 2, 3, 3]
77
B = [2, 3, 3, 4]
8-
C = [1, 2, 2, 2]
8+
C = [2, 3, 3, 4]
99
target = 7
1010
*/
1111
@@ -16,79 +16,69 @@
1616
import itertools
1717
from functools import partial
1818

19-
A = [1, 2, 3, 3]
20-
B = [2, 3, 3, 4]
21-
C = [1, 2, 2, 2]
22-
target = 7
23-
24-
25-
def construct_candidates(constructed_sofar):
26-
global A, B, C
27-
array = A
28-
if 1 == len(constructed_sofar):
29-
array = B
30-
elif 2 == len(constructed_sofar):
31-
array = C
32-
return array
33-
34-
35-
def over(constructed_sofar):
36-
global target
37-
sum = 0
38-
to_stop, reached_target = False, False
39-
for elem in constructed_sofar:
40-
sum += elem
41-
if sum >= target or len(constructed_sofar) >= 3:
42-
to_stop = True
43-
if sum == target and 3 == len(constructed_sofar):
44-
reached_target = True
45-
46-
return to_stop, reached_target
47-
48-
49-
def backtrack(constructed_sofar):
50-
to_stop, reached_target = over(constructed_sofar)
51-
if to_stop:
52-
if reached_target:
53-
print(constructed_sofar)
54-
return
55-
candidates = construct_candidates(constructed_sofar)
56-
for candidate in candidates:
57-
constructed_sofar.append(candidate)
58-
backtrack(constructed_sofar[:])
59-
constructed_sofar.pop()
60-
61-
62-
backtrack([])
63-
64-
65-
# Complexity: O(n(m+p))
66-
67-
# 1. Sort all the arrays - a,b,c. - This will improve average time complexity.
68-
# 2. If c[i] < Sum, then look for Sum - c[i] in array a and b. When pair found,
69-
# insert c[i], a[j] & b[k] into the result list. This can be done in O(n).
70-
# 3. Keep on doing the above procedure while going through complete c array.
71-
72-
73-
A = [1, 2, 3, 3]
74-
B = [2, 3, 3, 4]
75-
C = [1, 2, 2, 2]
76-
S = 7
77-
78-
79-
def check_sum(n, *nums):
80-
if sum(x for x in nums) == n:
81-
return (True, nums)
82-
else:
83-
return (False, nums)
84-
85-
86-
pro = itertools.product(A, B, C)
87-
func = partial(check_sum, S)
88-
sums = list(itertools.starmap(func, pro))
8919

90-
res = set()
91-
for s in sums:
92-
if s[0] is True and s[1] not in res:
93-
res.add(s[1])
94-
print(res)
20+
def array_sum_combinations(A, B, C, target):
21+
22+
def over(constructed_sofar):
23+
sum = 0
24+
to_stop, reached_target = False, False
25+
for elem in constructed_sofar:
26+
sum += elem
27+
if sum >= target or len(constructed_sofar) >= 3:
28+
to_stop = True
29+
if sum == target and 3 == len(constructed_sofar):
30+
reached_target = True
31+
return to_stop, reached_target
32+
33+
def construct_candidates(constructed_sofar):
34+
array = A
35+
if 1 == len(constructed_sofar):
36+
array = B
37+
elif 2 == len(constructed_sofar):
38+
array = C
39+
return array
40+
41+
def backtrack(constructed_sofar=[], res=[]):
42+
to_stop, reached_target = over(constructed_sofar)
43+
if to_stop:
44+
if reached_target:
45+
res.append(constructed_sofar)
46+
return
47+
candidates = construct_candidates(constructed_sofar)
48+
49+
for candidate in candidates:
50+
constructed_sofar.append(candidate)
51+
backtrack(constructed_sofar[:], res)
52+
constructed_sofar.pop()
53+
54+
res = []
55+
backtrack([], res)
56+
return res
57+
58+
59+
def unique_array_sum_combinations(A, B, C, target):
60+
"""
61+
1. Sort all the arrays - a,b,c. - This improves average time complexity.
62+
2. If c[i] < Sum, then look for Sum - c[i] in array a and b.
63+
When pair found, insert c[i], a[j] & b[k] into the result list.
64+
This can be done in O(n).
65+
3. Keep on doing the above procedure while going through complete c array.
66+
67+
Complexity: O(n(m+p))
68+
"""
69+
def check_sum(n, *nums):
70+
if sum(x for x in nums) == n:
71+
return (True, nums)
72+
else:
73+
return (False, nums)
74+
75+
pro = itertools.product(A, B, C)
76+
func = partial(check_sum, target)
77+
sums = list(itertools.starmap(func, pro))
78+
79+
res = set()
80+
for s in sums:
81+
if s[0] is True and s[1] not in res:
82+
res.add(s[1])
83+
84+
return list(res)

‎algorithms/backtrack/combination_sum.py‎

Lines changed: 12 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -16,18 +16,18 @@
1616
"""
1717

1818

19-
def combination_sum(self, candidates, target):
19+
def combination_sum(candidates, target):
20+
21+
def dfs(nums, target, index, path, res):
22+
if target < 0:
23+
return # backtracking
24+
if target == 0:
25+
res.append(path)
26+
return
27+
for i in range(index, len(nums)):
28+
dfs(nums, target-nums[i], i, path+[nums[i]], res)
29+
2030
res = []
2131
candidates.sort()
22-
self.dfs(candidates, target, 0, [], res)
32+
dfs(candidates, target, 0, [], res)
2333
return res
24-
25-
26-
def dfs(self, nums, target, index, path, res):
27-
if target < 0:
28-
return # backtracking
29-
if target == 0:
30-
res.append(path)
31-
return
32-
for i in range(index, len(nums)):
33-
self.dfs(nums, target-nums[i], i, path+[nums[i]], res)

‎algorithms/backtrack/expression_add_operators.py‎

Lines changed: 0 additions & 54 deletions
This file was deleted.

‎algorithms/backtrack/factor_combinations.py‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,8 @@
33
44
8 = 2 x 2 x 2;
55
= 2 x 4.
6-
Write a function that takes an integer n and return all possible combinations of its factors.
6+
Write a function that takes an integer n
7+
and return all possible combinations of its factors.
78
89
Note:
910
You may assume that n is always positive.
@@ -49,7 +50,7 @@ def get_factors(n):
4950

5051

5152
# Recursive:
52-
def get_factors_recur(n):
53+
def recursive_get_factors(n):
5354

5455
def factor(n, i, combi, combis):
5556
while i * i <= n:

0 commit comments

Comments
 (0)