Backtracking

Question 1

What is backtracking ??

Answer 1

In a given problem, if all possible solutions is to be found, then we can apply backtracking.

Question 2

What is bounded function or constraint ?

Answer 2

when finding the solution, there will be constraints can be enforced. Solution which satisfies the constraint will be considered as one of the solution. If the constraint is not met, the path/track will not be explored further. will move onto next possible solution.

Question 3

Which data structure used ?

Answer 3

State-space tree can be used to track the path traveled to find the solution

Question 4

Which algorithm most commonly used in backtracking ?

Answer 4

DFS with Recursive

Question 5

Backtracking problems

Answer 5

N-Queens problem
Maze
sudoku

Question 6

Backtracking Vs. Branch-and-Bound

Answer 6

Backtracking uses DFS to construct the solution

Branch and Bound used BFS.

Question 7

N Queens problem - Backtracking

Answer 7

• Problem
  Place ‘N’ queens in a N*N matrix.
• Constraints/ Bounded Functions
  
  • Queens cannot be placed in same row, column, diagonally.
• Start with Qi and place it in a matrix and place other queens by applying constraint for every move, if it satisfies move on to next queen, if not move to next place for the queen.

Question 8

Sum of subsets - Backtracking

Answer 8

• Problem
  In a given array of numbers and target sum, find all possible subset of numbers which adds upto exactly the target sum.
• Constraints
  
  • added weight cannot exceed target sum
  • remaining weight has to be greater than zero before exploring the path downwards.
• Approach.
  
  • maintain currSum , remainingSum
  • Add numbers from array by adding the weight to currSum and subtracting it from remaining sum. Before moving further down, apply boundary conditions.
    if remaining sum < targetSum, continue adding numbers.
    if remainingSum is > targetSum , try by not adding the number.