Added backtracking solutions

Meto Trajkovski · Meto Trajkovski · commit 9a03843e7b8a · 2019-12-12T18:56:04.000+01:00
diff --git a/Backtracking/generate_parentheses.py b/Backtracking/generate_parentheses.py
@@ -0,0 +1,59 @@
+'''
+Generate Parentheses
+
+Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
+
+Input: 3
+Output: 
+        [
+            '((()))',
+            '(()())',
+            '(())()',
+            '()(())',
+            '()()()'
+        ]
+
+=========================================
+This problem could be solved in several ways (using stack, queue, or just a simple list - see letter_combinations.py), all of them have the same complexity.
+I'll solve it using simple recursive algorithm.
+    Time Complexity:    O(4^N)      , O(2^(2*N)) = O(2^N)
+    Space Complexity:   O(4^N)
+'''
+
+
+############
+# Solution #
+############
+
+def generate_parentheses(n):
+    result = []
+    if n == 0:
+        return result
+
+    combinations(result, n, n, '')
+
+    return result
+
+
+def combinations(result, open_left, close_left, combination):
+    if close_left == 0:
+        # a new combination is created (no more open or close parentheses)
+        result.append(combination)
+    elif open_left == 0:
+        # no more open parentheses, so all left parentheses must be closed (just add the missing close parentheses)
+        result.append(combination + (')' * close_left))
+    else:
+        combinations(result, open_left - 1, close_left, combination + '(')
+
+        # check if there is a pair for this close parenthesis
+        if open_left < close_left:
+            combinations(result, open_left, close_left - 1, combination + ')')
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => ['((()))', '(()())', '(())()', '()(())', '()()()']
+print(generate_parentheses(3))
diff --git a/Backtracking/letter_combinations.py b/Backtracking/letter_combinations.py
@@ -0,0 +1,56 @@
+'''
+Letter Combinations of a Phone Number
+
+Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
+A mapping of digit to letters is just like on the telephone buttons. Note that 1 does not map to any letters.
+
+Input: '23'
+Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
+
+=========================================
+This problem could be solved in several ways (using recursion, stack, queue...) and the complexity is same in all, but this one has the simplest code.
+Iterate all digits and in each step look for the previous combinations, create a new 3 or 4 combinations from each combination using the mapping letters.
+    Time Complexity:    O(3^N * 4^M)    , N = number of digits that maps to 3 letters, M = number of digits that maps to 4 letters
+    Space Complexity:   O(3^N * 4^M)
+'''
+
+
+############
+# Solution #
+############
+
+def letter_combinations(digits):
+    if len(digits) == 0:
+        return []
+
+    mappings = {
+        '2': ['a','b','c'],
+        '3': ['d','e','f'],
+        '4': ['g','h','i'],
+        '5': ['j','k','l'],
+        '6': ['m','n','o'],
+        '7': ['p','q','r','s'],
+        '8': ['t','u','v'],
+        '9': ['w','x','y','z']
+    }
+    prev_combinations = ['']
+
+    for digit in digits:
+        new_combinations = []
+        for combination in prev_combinations:
+            # use the mappings and create new combinations
+            for mapping in mappings[digit]:
+                new_combinations.append(combination + mapping)
+        # save the newest combinations
+        prev_combinations = new_combinations
+
+    return prev_combinations
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
+print(letter_combinations('23'))
diff --git a/Backtracking/permutations.py b/Backtracking/permutations.py
@@ -0,0 +1,58 @@
+'''
+Permutations
+
+Given a collection of distinct integers, return all possible permutations.
+
+Input: [1,2,3]
+Output: 
+        [
+            [1,2,3],
+            [1,3,2],
+            [2,1,3],
+            [2,3,1],
+            [3,1,2],
+            [3,2,1]
+        ]
+
+=========================================
+A classical recursive algorithm for  permutations.
+    Time Complexity:    O(N!)
+    Space Complexity:   O(N!)
+'''
+
+
+############
+# Solution #
+############
+
+def permutations(nums):
+    result = []
+    if len(nums) == 0:
+        return result
+
+    permute(result, set(nums), [])
+
+    return result
+
+def permute(result, nums, permutation):
+    if len(nums) == 0:
+        result.append([num for num in permutation])
+    else:
+        for num in list(nums): # create a new object with the same values because nums will be changed later
+            nums.remove(num)
+            permutation.append(num)
+
+            permute(result, nums, permutation)
+
+            # reset the structures
+            del permutation[-1]
+            nums.add(num)
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
+print(permutations([1, 2, 3]))
diff --git a/Backtracking/power_set.py b/Backtracking/power_set.py
@@ -1,17 +1,17 @@
 '''
-The power set
+The Power Set
 
 The power set of a set is the set of all its subsets.
 Write a function that, given a set, generates its power set.
 
-Input: {1, 2, 3}
-Output: {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
+Input: [1, 2, 3]
+Output: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
 * You may also use a list or array to represent a set.
 
 =========================================
 Simple recursive combinations algorithm.
     Time Complexity:    O(Sum(C(I, N)))     , sum of all combinations between 0 and N = C(0, N) + C(1, N) + ... + C(N, N)
-    Space Complexity:   O(Sum(C(I, N)))     , this is for the result array, if we print the number then the space complexity will be O(1)
+    Space Complexity:   O(Sum(C(I, N)))     , this is for the result array, if we print the number then the space complexity will be O(N) (because of the recursive stack)
 '''
 
 
@@ -20,26 +20,24 @@
 ############
 
 def power_set(arr):
-    return combinations(arr, [], 0)
-
-# arr and taken are the same pointer always
-# the same arrays are used always
-def combinations(arr, taken, pos):
     result = []
-    result.append([arr[i] for i in taken]) # create the current combination
+    combinations(result, arr, [], 0)
+    return result
 
-    if len(arr) == pos:
-        return result
+# result, arr and taken are the same references always
+def combinations(result, arr, taken, pos):
+    result.append([arr[i] for i in taken]) # create the current combination
 
     n = len(arr)
+    if n == pos:
+        return
+
     # start from the last position (don't need duplicates)
     for i in range(pos, n):
         taken.append(i)
-        result += combinations(arr, taken, i + 1) # append the combinations
+        combinations(result, arr, taken, i + 1)
         del taken[-1] # return to the old state
 
-    return result
-
 
 ###########
 # Testing #
diff --git a/Backtracking/river_sizes.py b/Backtracking/river_sizes.py
@@ -17,7 +17,6 @@
 ]
 Output: [2, 1, 3, 1]
 
-
 =========================================
 This problem can be solved using DFS or BFS.
 If 1 is found, find all horizontal or vertical neighbours (1s), and mark them as 0.
diff --git a/README.md b/README.md
@@ -51,6 +51,7 @@ Solution 2 explanation
     Space Complexity:   O(X)
 '''
 
+
 ##############
 # Solution 1 #
 ##############
@@ -59,6 +60,7 @@ def name_of_solution_1(params):
     # description of code
     pass
 
+
 ##############
 # Solution 2 #
 ##############

Original file line number	Diff line number	Diff line change
`@@ -17,7 +17,6 @@`
`17`	`17`	`]`
`18`	`18`	`Output: [2, 1, 3, 1]`
`19`	`19`
`20`		`-`
`21`	`20`	`=========================================`
`22`	`21`	`This problem can be solved using DFS or BFS.`
`23`	`22`	`If 1 is found, find all horizontal or vertical neighbours (1s), and mark them as 0.`