Backracking | Data Structures & Algorithms Tutorials

Introduction

Backtracking is an algorithmic technique that involves recursively finding solutions to a problem by incrementally constructing potential solutions and abandoning those that do not meet the problem’s constraints.

These algorithms leverage a Depth First Search (DFS) approach and are typically employed in three types of problems:

1. Decision Problems: Seeking a feasible solution.
2. Optimization Problems: Seeking the best possible solution.
3. Enumeration Problems: Seeking all feasible solutions.

Examples

Get all subsets (Enumeration Problem)

Approach 1:

This approach involves recursively calling the same function to consider all possible subsets. For each index, there are two cases to consider: including the current element in the subset or excluding it.

Pseudocode:

1. If the end of the array is reached, add the current subset to the list of subsets.
2. Include the current element in the subset:

• Add the current element.
• Get all subsets after the current index.

1. Exclude the current element from the subset:

• Remove the current element.
• Get all subsets after the current index.

Approach 2:

This approach also involves recursively calling the same function to consider all subsets.

For each index:

1. Add the current subset.
2. Iterate over all elements from that index to the end. In each iteration:

• Include an element in the subset.
• Recursively call the function with the next index.
• Exclude the last inserted element.

Check if Subset Sum is Equal to Target (Decision Problem)

The approach involves recursively calling the same function to evaluate all possible subsets and determining if the sum of any subset equals the target. For each index, there are two scenarios to consider: including the current element in the subset or excluding it.

Find Subset with Minimum Sum (Optimization Problem)

This approach involves recursively calling the same function to evaluate all possible subsets and determining if the sum of any subset is less than the current minimum sum. For each index, there are two scenarios to consider: including the current element in the subset or excluding it.

Get All Permutations (Enumeration Problem)

The idea here is to generate each permutation by transforming the previous permutation.

Example

getAllPermutations("abcd"):

1. Start with ‘a’ + getAllPermutations("bcd"):

• ‘ab’ + getAllPermutations("cd"):
  • ‘abc’ + getAllPermutations("d") => ‘abcd’
  • ‘abd’ + getAllPermutations("c") => ‘abdc’
• ‘ac’ + getAllPermutations("bd"):
  • ‘acb’ + getAllPermutations("d") => ‘acbd’
  • ‘acd’ + getAllPermutations("b") => ‘acdb’
• ‘ad’ + getAllPermutations("bc"):
  • ‘adb’ + getAllPermutations("c") => ‘adbc’
  • ‘adc’ + getAllPermutations("b") => ‘adcb’

1. Continue with ‘b’ + getAllPermutations("acd"):

• ‘ba’ + getAllPermutations("cd"):
  • ‘bac’ + getAllPermutations("d") => ‘bacd’
  • ‘bad’ + getAllPermutations("c") => ‘badc’
• ‘bc’ + getAllPermutations("ad"):
  • ‘bca’ + getAllPermutations("d") => ‘bcad’
  • ‘bcd’ + getAllPermutations("a") => ‘bcda’
• ‘bd’ + getAllPermutations("ac"):
  • ‘bda’ + getAllPermutations("c") => ‘bdac’
  • ‘bdc’ + getAllPermutations("a") => ‘bdca’

1. Continue with ‘c’ + getAllPermutations("abd"):

• ‘ca’ + getAllPermutations("bd"):
  • ‘cab’ + getAllPermutations("d") => ‘cabd’
  • ‘cad’ + getAllPermutations("b") => ‘cadb’
• ‘cb’ + getAllPermutations("ad"):
  • ‘cba’ + getAllPermutations("d") => ‘cbad’
  • ‘cbd’ + getAllPermutations("a") => ‘cbda’
• ‘cd’ + getAllPermutations("ab"):
  • ‘cda’ + getAllPermutations("b") => ‘cdab’
  • ‘cdb’ + getAllPermutations("a") => ‘cdba’

1. Continue with ‘d’ + getAllPermutations("abc"):

• ‘da’ + getAllPermutations("bc"):
  • ‘dab’ + getAllPermutations("c") => ‘dabc’
  • ‘dac’ + getAllPermutations("b") => ‘dacb’
• ‘db’ + getAllPermutations("ac"):
  • ‘dba’ + getAllPermutations("c") => ‘dbac’
  • ‘dbc’ + getAllPermutations("a") => ‘dbca’
• ‘dc’ + getAllPermutations("ab"):
  • ‘dca’ + getAllPermutations("b") => ‘dcab’
  • ‘dcb’ + getAllPermutations("a") => ‘dcba’

Complexity Analysis

Time Complexity

Determining the time complexity of a backtracking solution can be challenging. We can estimate it by counting the number of different states our recursive code will compute and evaluating the operations within each recursive call. To find the exact runtime, we need to establish the recurrence relation and apply analysis techniques.

Example (Subset Problem)

• Number of states: (2^n)
• Number of operations in each call: Typically 1, and (n) in the terminating case (adding an array to the result).
• Total Time Complexity: (O(n \cdot 2^n))

Space Complexity

Space complexity depends on the amount of data stored for each state. If the problem isn’t an enumeration problem, we don’t maintain each state, so the space complexity is the maximum space required for any state.

For the Subset Problem, we store a maximum of (n) elements for each state, resulting in a space complexity of (O(n \cdot 2^n)).

Should You Use Backtracking to Solve a Given Problem?

Backtracking is suitable for problems with clear, well-defined constraints where solutions can be incrementally built and abandoned (“backtracked”) if they cannot be completed to a valid solution. However, not all such problems should be solved with backtracking, as it often leads to exponential time complexity and may not yield the most optimized solution.

If a problem can be solved using more efficient algorithmic techniques like Dynamic Programming or Greedy Algorithms, backtracking should be avoided. If no such solution exists, backtracking may be necessary.

Applications

Common problems that can be solved using backtracking include:

• Finding all subsets of an array.
• Finding all subsets of an array that meet a specific constraint (e.g., a defined sum of the subset).
• Finding all permutations of a string.
• Creating a Sudoku solver.
• Searching contacts by finding all letter combinations from telephone buttons given a few digits.
• Finding the path to exit a maze.
• Solving the Knapsack Problem/Resource Allocation.

Read More…

Heap and Hash : An Overview – https://kamleshsingad.com/heap-and-hash-an-overview/

Understanding SQL Joins: A Comprehensive Guide – https://kamleshsingad.com/understanding-sql-joins-a-comprehensive-guide/

Top 10 SQL Programming Tips for Beginners – https://kamleshsingad.com/top-10-sql-programming-tips-for-beginners/