Backtracking

Question 1

Backtracking

Answer 1

1. uses bruteforce search to solve the problem
2. We try to make all the possible solutions and pick out the best solutions from the desired solutions This is also done by dynamic programming but It is used for finding optimization problems
3. As the name suggests we’ll go back And come forward if it satisfies the condition then return success else we go back again
4. It is used to solve a problem in Which a sequence of objects is chosen from a specified set so that sequence satisfies some criteria
5. It is a systematic method of trying out various sequences of decisions until you find that works

Question 2

Terms related to backtracking— Nodes

Answer 2

1. **Live node **the notes that can be further generated are known as live nodes
2. E node whose children are being generated and become a successful node
3. Success node is set to be success node if it provides feasible solution
   4.** Dead node** the road which carried further generate and also does not provide feasible solution

Question 3

Difference between backtracking and recursion

Answer 3

1. Recurrence is a technique that calls the same function again and again Until reach the base case
2. Backtracking is an algorithm that finds all possible solutions and selects the desired one

Question 4

Applications of backtracking

Answer 4

1. N Queens problem
2. Colouring graph
3. sum of subsets problem
4. Hamilton cycle

Question 5

sum of subsets problem

Answer 5

1. most important problems in complexity theory
2. Here in the problem an array is given which contains a set of elements and And non empty subset is given as “M”
3. We need to choose the elements from the array which can sum up to M
4. We can solve this problem by dynamic approach and recursive Method
5. o(2n)

Question 6

Recursive method of solving sum of subsets problem

Answer 6

We have two options while solving it at every step:
1. Include : here we include means we are selecting the element from our next line
2. Reject(exclude) : We’re rejecting the elements from the array

1. Now we consider the first element and cheque the difference between required sum and the first element Likewise we perform this for the every Element of the array and we either select it or reject it and form a tree with both selecting and rejecting the elements
2. From the whole tree we Calculate which forms the required result and selectthem

Question 6

sum of subsets algo

Answer 6

def subset_sum(arr, res, sum)
if sum ==0
return true
if sum < 0
return false
if len(arr) == 0 and sum!= 0
return false
arr.pop(0);
if len(arr) > 0
res.append(arr[0])
select = subset_sum(arr, sum-arr[0], res)
reject = subset_sum(arr, res, sum)
return reject or sum

Question 7

n-queens problem

Answer 7

1. End Queen’s problem is to place end Queens in such a manner On an n x n Chessboard that no queens attack each other by being in same rowon diagonal or column
2. It can be see that if N =1 The problem has trivial solution, n=2, n=3 No solution exists so we’ll consider N=4 Queen’s problem to generate it to end Queens problem

The possible solution for 4-queens problem is:
(2, 4 1, 3) or
(3, 1, 4, 2)

The possible solution for 8- queens problem is:
(4,6,8,2,7,6,5)

Question 8

Graph colour

Answer 8

1. The goal is to assign colours to the vertices such that move to adjacent Vertices share the same colour
2. Start with empty colouring For the graph and set the current vertex as the first vertex in the graph
3. Now select a Colour and cheque whether it is valid or not that is it doesnt conflict with any adjacent vertices
4. Is a valid colour is found move to the next vertex
5. Is the valid colour is not found, Backtrack to the previous vertex and try different colour repeat this process until you 5 day valid colour for all vertices or determine that no valid colour exists
6. Here backtracking is used when you reach a point where you cannot find a valid colour for a current one mix we need to backtrack to the previous vertex and try another colour
7. Continue the process until you have assigned to all vertexes or you have explored all possibilities and determine the true valid colour exists
8. The The output should be if it is valid should be returned or else return a message indicating that valid colouring is not possible