Lecture_Notes/imperfect_notes/Recursion and Backtracking/1.md

Recursion
----------
Recursion - process of function calling itself
 directly or indirectly. 

 __Steps involved:__ 
- Base case
- Self Work
- Recursive Calls

```python
def fib(n):
    if n <= 1 : return n  # base case
    return fib(n-1) + fib(n-2) # recursive calls
    
fib(10)  # initial call
```
In the recursive program, the solution to the base case is provided and the solution of the bigger problem is expressed in terms of smaller problems.
In the above example, base case for n < = 1 is defined and larger value of number can be solved by converting to smaller one till base case is reached.

__Intuition__

The  main idea is to represent a problem in terms of one or more smaller problems, and add one or more base conditions that stop the recursion. 
_For example_, we compute factorial n if we know factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0.


Power
-----

> Given n, k.  Find $n^k$

```python
def pow(n, k):
    if k == 0: return 1
    return n*pow(n, k - 1)
```
__Time Complexity__: O(n)

__Optimised solution:__
```python
def pow(n, k):
    if k == 0: return 1
    
    nk = pow(n, k//2)
    if k % 2 == 0:
        return nk * nk
    else:
        return nk * nk * n
```

Why not f(n, k/2) * f(n, k/2+1) in the else condition? 
To allow reuse of answers. 

<img src="https://user-images.githubusercontent.com/35702912/66316190-d30e1f00-e934-11e9-8089-85c6dc69baa7.jpg" data-canonical-src="https://user-images.githubusercontent.com/35702912/66316190-d30e1f00-e934-11e9-8089-85c6dc69baa7.jpg" width="500" />

__Time Complexity__ (assuming all multiplications are O(1))? O(\log_2 k)$O(\log_{2}k)$


Break it into 3 parts? k//3 and take care of mod1 and mod2.

Binary is still better, just like in binary search.

-- --
All Subsets
-----------

> Given A[N], print all subsets

The idea is to consider two cases for every element. 
(i) Consider current element as part of current subset.
(ii) Do not consider current element as part of current subset.

Number of subsets? $2^{n}$

Explain that we want combinations, and not permutations. [1, 4] = [4, 1]

Number of permutations will be much larger than combinations. 

```python
def subsets(A, i, aux):
    if i == len(A):
        print(aux)
        return
    take = subsets(A, i+1, aux + [A[i]]) # Case 1
    no_take = subsets(A, i+1, aux) # Case 2
```


<img src="https://user-images.githubusercontent.com/35702912/66323471-7a914e80-e941-11e9-84a9-11a333ac4f77.jpg" width="500" 
/> 

How many leaf nodes? $2^n$ - one for each subset
How many total nodes? $2^{n+1} - 1$

__Time Complexity__: $O(2^n)$

Subsets using Iteration
-----------------------

Look at recursion Tree. 
Going left = 0
Going right = 1

Basically, for each element, choose = 1, skip = 0

So, generate numbers from 0 to $2^n-1$ and look at the bits of the numbers. Each subset is formed using each number. 
```
For A = [1 2 3]

000        []
001        [c] 
010        [b] 
011        [b c]
100        [a]
101        [a c]
110        [a b] 
111        [a b c]
```

Lexicographic subsets
---------------------

Explain what is lexicographic order. 

```
For Array [0,1,2,3,4] Subsets in Lexicographical order,
[]
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 3]
[0, 2]
[0, 2, 3]
[0, 3] 
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]
``` 
- The idea is to sort the array first. 
- After sorting, one by one fix characters and recursively generates all subsets starting from them. 
- After every recursive call, we remove current character so that next permutation can be generated.
 - Basically, we're doing DFS. Print when encountering node
But don't print when going left - because already printed in parent. 


<img src="https://user-images.githubusercontent.com/35702912/66468106-3d44d200-eaa3-11e9-96e7-c6a050be1219.jpg" width="500" 
/> 


<img src="https://user-images.githubusercontent.com/35702912/66468119-42098600-eaa3-11e9-8f24-237be2a91d12.jpg" width="500" 
/> 
```python
def subsets(A, i, aux, p):
    if p: print(aux)
    if i == len(A):
        return
    take = subsets(A, i+1, aux + [A[i]], True)
    no_take = subsets(A, i+1, aux, False)
```

__Time Complexity__: $O(2^n)$ <br>
__Space Complexity__: $O(n^2)$, because we're creating new aux arrays.

-- --
Number of Subsets with a given Sum
--------------------

> Given an array of integers and a sum, the task is to print all subsets of given array with sum equal to given sum.
> A = [2, 3, 5, 6, 8, 10]        Sum = 10
> Output:  [5, 2, 3] [2, 8] [10]

The subsetSum problem can be divided into two subproblems.   
- Include the current element in the sum and recur (i = i + 1) for the rest of the array
-  Exclude the current element from the sum and recur (i = i + 1) for the rest of the array. 


<img src="https://user-images.githubusercontent.com/35702912/66469192-11c2e700-eaa5-11e9-9094-252ce842464a.jpg" width="500" 
/> 
```python
def subsetSum(A,N,cur_sum, i, target):
    if i == N:
        if cur_sum == target:
            return 1
        else :
            return 0
    take = subsetSum(A,N,cur_sum + A[i], i+1, target)
    no_take = subsetSum(A,N,cur_sum, i+1, target)
    return take + no_take
```

Why can't terminate earlier when cur_sum == target? 
Because we can have negative values in the array as well and this condition will prevent us from considering negative values. 
For eg, 
target = 6
1, 2, 3 is good, but
1, 2, 3, -1, 1 is also good. 
__Time Complexity__:  $O(2^n)$
__Space Complexity__: $O(n)$

Number of Subsets with a given Sum (Repetition Allowed)
---------------
> Given a set of m distinct positive integers and a value ‘N’. The problem is to count the total number of ways we can form ‘N’ by doing sum of the array elements. Repetitions and different arrangements are allowed.
> All array elements are positive. 

The subsetSum2 problem can be divided into two subproblems.   
- Include the current element in the sum and recur for the rest of the array. Here the value of i is not incremented to incorporate the condition of including multiple occurances of a element. 
-  Exclude the current element from the sum and recur (i = i + 1) for the rest of the array. 

<img src="https://user-images.githubusercontent.com/35702912/66470200-c27db600-eaa6-11e9-8744-ca572d6000e1.jpg" width="500" 
/> 

```python
def subsetSum2(A,N,cur_sum, i, target):
    if i == N:
        if cur_sum == target:
            return 1
        else :
            return 0
    elif cur_sum > target:
        return 0;
    take = subsetSum2(A,N,cur_sum + A[i], i, target)
    no_take = subsetSum2(A,N,cur_sum, i+1, target)
    return take + no_take
```
__Time Complexity__ :  $O(2 ** (Target/MinElement))$ <br>
__Space Complexity__:  $O(Target/Min Element)$