Why Backtracking and What Greedy Cannot Solve in DSA Python - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a subset sums to target using backtracking.

DSA Python

def subset_sum(nums, target, index=0):
    if target == 0:
        return True
    if index == len(nums) or target < 0:
        return False
    # Include nums[index]
    if subset_sum(nums, target - nums[index], index + 1):
        return True
    # Exclude nums[index]
    return subset_sum(nums, target, [1])

Drag options to blanks, or click blank then click option'

Atarget

Bindex

C0

Dindex + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Not increasing the index causes infinite recursion.

Using target instead of index in recursive call.

We move to the next index when excluding the current number to explore other subsets.

2fill in blank

medium

Complete the code to find the maximum sum of non-adjacent elements using greedy approach.

DSA Python

def max_non_adjacent_sum(nums):
    incl = 0
    excl = 0
    for num in nums:
        new_excl = max(incl, excl)
        incl = excl + num
        excl = [1]
    return max(incl, excl)

Drag options to blanks, or click blank then click option'

Anew_excl

Bnum

Cincl

Dexcl

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning excl to num causes wrong sums.

Not updating excl leads to incorrect results.

We update excl to the maximum of previous incl and excl to avoid adjacent picks.

3fill in blank

hard

Fix the error in the backtracking code to generate all permutations of a list.

DSA Python

def permute(nums, path, used, res):
    if len(path) == len(nums):
        res.append(path[:])
        return
    for i in range(len(nums)):
        if used[i]:
            continue
        used[i] = True
        path.append(nums[i])
        permute(nums, path, used, res)
        path.pop()
        [1] = False

Drag options to blanks, or click blank then click option'

Apath[i]

Bused[i]

Cnums[i]

Dres[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Not resetting used[i] causes missing permutations.

Resetting wrong variable leads to errors.

We must reset used[i] to False after backtracking to allow reuse of that element.

4fill in blank

hard

Fill both blanks to complete the backtracking code that solves the N-Queens problem.

DSA Python

def is_safe(board, row, col, n):
    for i in range(row):
        if board[i] == col or abs(board[i] - col) == row - i:
            return False
    return True

def solve_n_queens(n, board=[], row=0, solutions=[]):
    if row == n:
        solutions.append(board[:])
        return
    for col in range(n):
        if is_safe(board, row, col, n):
            board.append([1])
            solve_n_queens(n, board, [2], solutions)
            board.pop()

Drag options to blanks, or click blank then click option'

Acol

Brow + 1

Crow

Dcol + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Appending row instead of col causes wrong board state.

Not incrementing row leads to infinite recursion.

We add the current column to board and move to the next row (row + 1) in recursion.

5fill in blank

hard

Fill all three blanks to complete the code that demonstrates greedy failure on coin change problem.

DSA Python

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount [1] coin:
            amount [2]= coin
            count [3] 1
    return count

Drag options to blanks, or click blank then click option'

A>=

B-=

C+=

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' instead of '>=' causes wrong loop condition.

Using '+=' instead of '-=' reduces amount incorrectly.

We use '>=' to check if coin fits, '-=' to reduce amount, and '+=' to count coins.

Practice

1. Why is backtracking preferred over greedy algorithms in problems like the N-Queens puzzle?

easy

A. Because greedy algorithms never use recursion

B. Because greedy algorithms always find the optimal solution quickly

C. Because backtracking uses less memory than greedy algorithms

D. Because backtracking explores all possible solutions and can backtrack on wrong choices

Solution

1. Step 1: Understand the problem nature

   The N-Queens puzzle requires placing queens so none attack each other, needing exploration of many possibilities.

2. Step 2: Compare backtracking and greedy approaches

   Backtracking tries all options and undoes wrong choices, while greedy picks locally best choices that may fail globally.

3. Final Answer:

   Because backtracking explores all possible solutions and can backtrack on wrong choices -> Option D

4. Quick Check:

   Backtracking explores all options = A [OK]

Hint: Backtracking tries all paths; greedy picks only best immediate choice [OK]

Common Mistakes:

• Thinking greedy always finds the best solution
• Confusing backtracking with dynamic programming
• Assuming backtracking uses less memory

2. Which of the following is the correct syntax to start a backtracking function in Python?

easy

A. def backtrack(path, options):

B. function backtrack(path, options) {

C. backtrack(path, options) => {

D. def backtrack[]:

Solution

1. Step 1: Identify Python function syntax

   Python functions start with 'def', followed by name and parameters in parentheses, ending with a colon.

2. Step 2: Check each option

   def backtrack[]: uses invalid square brackets instead of parentheses; function backtrack(path, options) { and backtrack(path, options) => { are JavaScript syntax; def backtrack(path, options): is the correct Python syntax.

3. Final Answer:

   def backtrack(path, options): -> Option A

4. Quick Check:

   Python function syntax = D [OK]

Hint: Python functions start with 'def' and end with ':' [OK]

Common Mistakes:

• Using JavaScript or other language syntax
• Missing colon at function end
• Using square brackets instead of parentheses

3. What will be the output of the following Python code snippet?

def backtrack(nums, path):
    if not nums:
        print(path)
        return
    for i in range(len(nums)):
        backtrack(nums[:i] + nums[i+1:], path + [nums[i]])

backtrack([1, 2], [])

medium

A. [2, 1]

B. [1, 2]

C. [1, 2]\n[2, 1]

D. []

Solution

1. Step 1: Understand the backtracking function

   The function generates all permutations of the list by choosing each element and recursing on the rest.

2. Step 2: Trace the calls for input [1, 2]

   First call picks 1, then 2 left, prints [1, 2]. Second call picks 2, then 1 left, prints [2, 1].

3. Final Answer:

   [1, 2] [2, 1] -> Option C

4. Quick Check:

   Permutations of [1, 2] = [1, 2] and [2, 1] [OK]

Hint: Backtracking here prints all permutations of the list [OK]

Common Mistakes:

• Thinking it prints only one permutation
• Confusing slicing syntax
• Missing that print happens when nums is empty

4. Find the error in this backtracking code for subset generation:

def subsets(nums, path=[]):
    print(path)
    for i in range(len(nums)):
        subsets(nums[i+1:], path.append(nums[i]))

subsets([1, 2])

medium

A. Using mutable default argument for path causes unexpected behavior

B. Missing return statement in function

C. Incorrect slicing of nums in recursive call

D. Using print inside recursion is invalid

Solution

1. Step 1: Identify mutable default argument issue

   Using path=[] as default causes the same list to be shared across calls, leading to wrong subsets.

2. Step 2: Check recursive call usage

   path.append(nums[i]) modifies path in place and returns None, so recursive call gets None instead of list.

3. Final Answer:

   Using mutable default argument for path causes unexpected behavior -> Option A

4. Quick Check:

   Mutable default args cause bugs = A [OK]

Hint: Avoid mutable defaults like lists in function parameters [OK]

Common Mistakes:

• Ignoring mutable default argument problem
• Thinking print inside recursion is wrong
• Assuming missing return causes error here

5. Which problem below cannot be solved correctly by a greedy algorithm but requires backtracking to find all solutions?

A) Finding minimum number of coins for change when coin denominations are unlimited and standard
B) Finding all subsets of a set
C) Finding shortest path in a weighted graph with non-negative edges
D) Sorting an array in ascending order

hard

A. Finding minimum number of coins for change when coin denominations are unlimited and standard

B. Finding all subsets of a set

C. Finding shortest path in a weighted graph with non-negative edges

D. Sorting an array in ascending order

Solution

1. Step 1: Analyze each problem type

   A) Greedy works for standard coin change; C) Dijkstra's algorithm is greedy and works; D) Sorting uses greedy-like comparisons.

2. Step 2: Identify problem needing backtracking

   Finding all subsets requires exploring all combinations, which greedy cannot do; backtracking is needed.

3. Final Answer:

   Finding all subsets of a set -> Option B

4. Quick Check:

   All subsets need backtracking = B [OK]

Hint: All subsets require exploring all options, not greedy choice [OK]

Common Mistakes:

• Thinking greedy can find all subsets
• Confusing shortest path with subset generation
• Assuming sorting needs backtracking