Backtracking - DSA Interview Questions

Backtracking is a powerful algorithmic technique used for solving recursive problems by exploring all possible solutions and pruning those that fail constraints. It is commonly used in combinatorial problems, such as permutations, combinations, Sudoku solving, and pathfinding. Mastering backtracking is essential for efficiently tackling complex coding interview problems.

Practice Backtracking DSA Coding Problems with Solutions

Learning Objectives:

Understand how backtracking systematically explores and prunes solution spaces to solve recursive problems. Learn to apply backtracking to problems like permutations, subset generation, graph traversal, and constraint satisfaction.

Exercise Instructions:

Start with the first problem and attempt to solve it before checking the hint or solution.
Ensure you understand the logic behind each solution, as this will help you with more complex problems.
Use these exercises to reinforce your learning and identify areas that may require further study.

1. Generate All Subsets of a Set

Required Input:

[1, 2, 3]

Expected Output:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Code In Python

def generate_subsets(nums): # Write your logic here pass # Prefilled input nums = [1, 2, 3] print(generate_subsets(nums))

Run Code?

Click Run Button to view compiled output

2. Generate All Permutations of a String

Required Input:

abc'

Expected Output:

['abc', 'acb', 'bac', 'bca', 'cba', 'cab']

Code In Python

def generate_permutations(s): # Write your logic here pass # Prefilled input s = 'abc' print(generate_permutations(s))

Run Code?

Click Run Button to view compiled output

3. Find All Unique Combinations That Sum to a Target

Required Input:

[2, 3, 6, 7], target=7

Expected Output:

[[2, 2, 3], [7]]

Code In Python

def combination_sum(candidates, target): # Write your logic here pass # Prefilled input candidates = [2, 3, 6, 7] target = 7 print(combination_sum(candidates, target))

Run Code?

Click Run Button to view compiled output

4. Find All Unique Combinations That Sum to a Target (Without Repetition)

Required Input:

[10, 1, 2, 7, 6, 1, 5], target=8

Expected Output:

[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

Code In Python

def combination_sum_unique(candidates, target): # Write your logic here pass # Prefilled input candidates = [10, 1, 2, 7, 6, 1, 5] target = 8 print(combination_sum_unique(candidates, target))

Run Code?

Click Run Button to view compiled output

5. Word Search in a Grid

Required Input:

[['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], word='ABCCED'

Expected Output:

True

Code In Python

def exist(board, word): # Write your logic here pass # Prefilled input board = [ ['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E'] ] word = 'ABCCED' print(exist(board, word))

Run Code?

Click Run Button to view compiled output

6. Generate Balanced Parentheses

Required Input:

n=3

Expected Output:

['((()))', '(()())', '(())()', '()(())', '()()()']

Code In Python

def generate_parentheses(n): # Write your logic here pass # Prefilled input n = 3 print(generate_parentheses(n))

Run Code?

Click Run Button to view compiled output

7. Find All Palindromic Partitions of a String

Required Input:

aab'

Expected Output:

[['a', 'a', 'b'], ['aa', 'b']]

Code In Python

def partition_palindromes(s): # Write your logic here pass # Prefilled input s = 'aab' print(partition_palindromes(s))

Run Code?

Click Run Button to view compiled output

8. Find All Letter Case Permutations of a String

Required Input:

a1b2'

Expected Output:

['a1b2', 'a1B2', 'A1b2', 'A1B2']

Code In Python

def letter_case_permutation(s): # Write your logic here pass # Prefilled input s = 'a1b2' print(letter_case_permutation(s))

Run Code?

Click Run Button to view compiled output

9. Find All Unique Subsets with Duplicates

Required Input:

[1, 2, 2]

Expected Output:

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

Code In Python

def subsets_with_dup(nums): # Write your logic here pass # Prefilled input nums = [1, 2, 2] print(subsets_with_dup(nums))

Run Code?

Click Run Button to view compiled output

10. Find All Paths in a Maze

Required Input:

[[1, 1, 0], [1, 1, 1], [0, 1, 1]]

Expected Output:

[['Down', 'Right', 'Down', 'Right'], ['Down', 'Right', 'Right', 'Down'], ['Right', 'Down', 'Down', 'Right'], ['Right', 'Down', 'Right', 'Down']]

Code In Python

def find_maze_paths(maze): # Write your logic here pass # Prefilled input maze = [ [1, 1, 0], [1, 1, 1], [0, 1, 1] ] print(find_maze_paths(maze))

Run Code?

Click Run Button to view compiled output

1 of 3