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

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

def pow(n, k):
    if k == 0: return 1
    return n*pow(n, k - 1)

Time Complexity: O(n)

Optimised solution:

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.

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.

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

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.

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)
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.

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.

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))
Space Complexity: O(Target/Min Element)