Why Backtracking and What Greedy Cannot Solve in DSA C - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking for Subset Sum Problem

What is the output of the following C code that uses backtracking to find subsets summing to 5?

DSA C

#include <stdio.h>

int arr[] = {1, 2, 3, 4};
int n = 4;
int target = 5;

void backtrack(int start, int sum) {
    if (sum == target) {
        printf("Found subset with sum 5\n");
        return;
    }
    if (sum > target || start == n) return;
    backtrack(start + 1, sum + arr[start]);
    backtrack(start + 1, sum);
}

int main() {
    backtrack(0, 0);
    return 0;
}

A

Found subset with sum 5
Found subset with sum 5

B

Found subset with sum 5
Found subset with sum 5
Found subset with sum 5

C No output

D

Found subset with sum 5

💡 Hint

Think about how many subsets sum to 5 in the array {1,2,3,4}.

The subsets {1,4} and {2,3} both sum to 5, so the message prints twice.

🧠 Conceptual

intermediate

Why Greedy Fails for the Subset Sum Problem

Why does a greedy approach fail to solve the subset sum problem correctly in all cases?

A Because greedy uses recursion which is inefficient for subset sum.

B Because greedy always finds the global solution but is slower than backtracking.

C Because greedy picks local best choices which may not lead to a global solution.

D Because greedy requires sorting the array which is impossible for subset sum.

💡 Hint

Consider if picking the largest number first always leads to a correct subset.

Greedy picks the largest or smallest element first without considering future choices, so it can miss valid subsets.

🔧 Debug

advanced

Identify the Error in Greedy Coin Change Algorithm

What error does the following greedy coin change code produce when trying to make change for 6 with coins {1, 3, 4}?

DSA C

int coins[] = {4, 3, 1};
int n = 3;
int amount = 6;
int count = 0;

for (int i = 0; i < n; i++) {
    while (amount >= coins[i]) {
        amount -= coins[i];
        count++;
    }
}
printf("Coins used: %d\n", count);

A Runtime error

B Coins used: 2

C Coins used: 6

D Coins used: 3

💡 Hint

Check how the greedy picks coins starting from the largest coin.

Greedy picks one 4 coin and then two 1 coins, total 3 coins, but optimal is two coins (3+3).

❓ Predict Output

advanced

Output of Backtracking for N-Queens Partial Solution Count

What is the output of this C code that counts partial solutions for 4-Queens problem using backtracking?

DSA C

#include <stdio.h>
#include <stdlib.h>

int count = 0;
int board[4];

int is_safe(int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i] == col || abs(board[i] - col) == row - i) return 0;
    }
    return 1;
}

void solve(int row) {
    if (row == 4) {
        count++;
        return;
    }
    for (int col = 0; col < 4; col++) {
        if (is_safe(row, col)) {
            board[row] = col;
            solve(row + 1);
        }
    }
}

int main() {
    solve(0);
    printf("Total solutions: %d\n", count);
    return 0;
}

A Total solutions: 1

B Total solutions: 2

C Total solutions: 4

D Total solutions: 0

💡 Hint

Recall the known number of solutions for 4-Queens problem.

The 4-Queens problem has exactly 2 distinct solutions found by backtracking.

🧠 Conceptual

expert

Why Backtracking is Needed When Greedy Fails

Which statement best explains why backtracking is necessary for problems where greedy algorithms fail?

A Backtracking explores all possible choices to find the correct solution, while greedy only picks local best choices.

B Backtracking always runs faster than greedy algorithms by pruning unnecessary paths.

C Backtracking uses dynamic programming internally to optimize greedy solutions.

D Backtracking converts problems into linear ones so greedy can solve them.

💡 Hint

Think about how backtracking handles choices compared to greedy.

Backtracking tries all options and backtracks on wrong paths, ensuring global correctness unlike greedy.