Backtracking | Algorithmic Apporoach

Backtracking solves a similar problems as what dynamic programming solves. The only thing about backtracking is that we care about returning all of the solutions. So if we are asked to generate all of the possible paths or solutions in a problem, theres's a good chance that it's a backtracking problem.

Alternatively, it could also be that we want to return a valid solution amongst all solutions.

What this means is that given a type of question that is asking us for a valid solution amongst all the solutions. If you can tell from the question that there are certain constraints in play that prevent all of the solutions from being correct, only a couple of them are correct.

This is different from an optimisation question because in an optimisation question there is usually only one solution amongst all the solutions.

When it comes to backtracking with this valid solution, there might be multiple valid solutions. You have to return the first one that is valid but you still want to generate all of the possible solutions that exist because maybe only one of them is valid.

This is the idea behind when backtracking is the appropriate approach to solve a question.

Some of the question which implement backtracking:

1. https://neetcode.io/problems/generate-parentheses
2. https://leetcode.com/problems/sudoku-solver/description/

The framework of Backtracking is:

1. Brute force
2. Recursive

Let's practice it:

Generate Parentheses

You are given an integer n. Return all well-formed parentheses strings that you can generate with n pairs of parentheses.

Example 1:

Input: n = 1

Output: ["()"]

Example 2:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

You may return the answer in any order.

Constraints:

• 1 <= n <= 7

Derivations:

1. We know we need a our string size of n * 2, for example ,n = 3. Valid results had a size of 6 i.e "((()))"
2. Any time we have a openBracket we need a closing one
3. i.e "(", must need a ")"

backTracking(n, currentString, openCount, closeCount, result){
 if(currentString.length === n){
	result.push(currentString)
	return
 }

// Ensures we only add an opening parenthesis ( if there are
// unused opening parentheses left.

 if(openCount > 0){
    backTracking(n, currentString + "(",openCount - 1, 
    closeCount, result)
 }

// Adding a ) is valid only if there are unmatched ( in the 
// current string

 if(closeCount > openCount){
   backTracking(n, currentString + ")", openCount,
   closeCount - 1 , result
 }
}

let results =[]
backTracking(n, "", n ,n, results) 

Further intuition:

//  Base case
if(n * 2 === solution.length){
        result.push(solution)
        return
}

//what does n has to do here?
//opening goes first
// how many opening bracket can be used ? extacly n
// we cannot change n, as base case depends on n
if(openCount > 0){
 backTrack(solution + "(", n, result, openCount - 1, closeCount)
}

// if we have 3 open we can have 3 count, 
// but we we have only 2 open left, 
// then we can only have 2 count left
if(closeCount > openCount){
 backTrack(solution + ")", n, result, openCount, closeCount -1)
}