Lecture_Notes/imperfect_notes/Recursion and Backtracking/2.md

Backtracking
------------

Backtracking is a methodical way of trying out various sequences of decisions, until you find one that “works”. It is a systematic way to go through all the possible configurations of a search space.
- do
- recurse
- undo

Backtracking is easily implemented with recursion because:
- The run-time stack takes care of keeping track of the choices that got us to a given point.
- Upon failure we can get to the previous choice simply by returning a failure code from the recursive call.

Backtracking can help reduce the space complexity, because we're reusing the same storage. 

__Backtracking Algorithm__: 
Backtracking is really quite simple--we “explore” each node, as follows:  
```python
To “explore” node N: 
1. If N is a goal node, return “success” 
2. If N is a leaf node, return “failure” 
3. For each child C of N, 
	3.1. Explore C 
		3.1.1. If C was successful, return “success” 
 4. Return “failure”
```
Print all Permutations of a String
-------------
> A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered string S into a one-to-one correspondence with S itself. <br>
String: ABC <br>
Permutations: ABC ACB BAC BCA CBA CAB

Total permutations =  n!

<img src="https://user-images.githubusercontent.com/35702912/66570095-7e63e180-eb8a-11e9-8e3c-31d8e04f2d67.jpg" width="500" 
/> 
<img src="https://user-images.githubusercontent.com/35702912/66570104-83c12c00-eb8a-11e9-802d-f0f0ede4a14a.jpg" width="500" 
/> 


```python
def  permute(S, i):
	if i == len(S):
		print(S)
	for j in  range(i, len(S)):
		S[i], S[j] = S[j], S[i]
		permute(S, i+1)
		S[i], S[j] = S[j], S[i] # backtrack
```
__Time Complexity:__ _O(n*n!)_ because there are n! permutations and it requires _O(n)_ to print a permutation.
<br>
__Space Complexity:__ _O(n)_

_Note: Output not in Lexicographic Order._

Print all Unique Permutations of a String
--------------------
> String: AAB
> Permutations: AAB ABA BAA

Basically, if we're swapping S[i] with S[j], but S[j] already occured earlier from S[i] .. S[j-1], then swapping will result in repetition. 


<img src="https://user-images.githubusercontent.com/35702912/66570690-bc153a00-eb8b-11e9-8a00-9dfb728df5f9.jpg" width="500" 
/> 

```python
def  permute_distinct(S, i):
if i == len(S):
	print(S)
for j in  range(i, len(S)):
	if S[j] in S[i:j]:
		continue
	S[i], S[j] = S[j], S[i]
	permute_distinct(S, i+1)
	S[i], S[j] = S[j], S[i] # backtrack
```
__Time Complexity:__  _O(n*n!)_ <br>
__Space Complexity:__ _O(n)_

Print Permutations Lexicographically
---
> Given a string, print all permutations of it in sorted order. <br>
For example, if the input string is “ABC”, then output should be “ABC, ACB, BAC, BCA, CAB, CBA”.

- Right shift the elements before making the recursive call.
- Left shift the elements while backtracking. 

```python
def  permute(S, i):
	if i == len(S):
		print(S)
	for j in  range(i, len(S)):
		S[i], S[j] = S[j], S[i]
		permute(S, i+1)
		S[i], S[j] = S[j], S[i] # backtrack
```

__Time Complexity:__  _O(n* n*n!)_ <br>
__Space Complexity:__ _O(n)_

Kth Permutation Sequence (Optional)
----
> Given a string of length n containing lowercase alphabets only. You have to find the k-th permutation of string lexicographically.


$\dfrac{k}{(n-1)!}$ will give us the index of the first digit. Remove that digit, and continue. 

```python
def  get_perm(A, k):
	perm = []
	while A:
		# get the index of current digit
		div = factorial(len(A)-1)
		i, k = divmod(k, div)
		perm.append(A[i])
		# remove handled number
		del A[index]
return perm
```



Sorted Permutation Rank (Optional)
--
> Given S, find the rank of the string amongst its permutations sorted lexicographically.
Assume that no characters are repeated.

```
Input : 'acb'
Output : 2
Explanation:
The order permutations with letters 'a', 'c', and 'b' :
abc
acb
bac
bca
cab
cba
```
**Hint:**
If the first character is X, all permutations which had the first character less than X would come before this permutation when sorted lexicographically.

Number of permutation with a character C as the first character = number of permutation possible with remaining $N-1$ character = $(N-1)!$

**Approach:**
rank = number of characters less than first character * (N-1)! + rank of permutation of string with the first character removed
```
Lets say out string is “VIEW”.
Character 1 : 'V'
All permutations which start with 'I', 'E' would come before 'VIEW'.
Number of such permutations = 3! * 2 = 12
Lets now remove ‘V’ and look at the rank of the permutation ‘IEW’.

Character 2 : ‘I’
All permutations which start with ‘E’ will come before ‘IEW’
Number of such permutation = 2! = 2.
Now, we will limit ourself to the rank of ‘EW’.

Character 3:
‘EW’ is the first permutation when the 2 permutations are arranged.
So, we see that there are 12 + 2 = 14 permutations that would come before "VIEW".
Hence, rank of permutation = 15.
```