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.

Practice

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

easy

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

B. Because greedy algorithms always find the optimal solution quickly

C. Because backtracking uses less memory than greedy algorithms

D. Because greedy algorithms do not use recursion

Solution

1. Step 1: Understand problem requirements

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

2. Step 2: Compare algorithm 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 A

4. Quick Check:

   Backtracking explores all options = A [OK]

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

Common Mistakes:

• Thinking greedy always finds the best solution
• Confusing memory use between backtracking and greedy
• Assuming backtracking is always slower without context

2. Which of the following is the correct syntax to start a backtracking function in C for solving a problem recursively?

easy

A. int backtrack[] = {0};

B. void backtrack(int step) { /* code */ }

C. backtrack() -> void { /* code */ }

D. function backtrack(int step) { /* code */ }

Solution

1. Step 1: Identify valid C function syntax

   In C, functions are declared with return type, name, and parameters inside parentheses.

2. Step 2: Check each option

   A matches C syntax; B is an array declaration; C and D use non-C syntax.

3. Final Answer:

   void backtrack(int step) { /* code */ } -> Option B

4. Quick Check:

   C function syntax = A [OK]

Hint: C functions start with return type and parentheses [OK]

Common Mistakes:

• Using JavaScript or other language syntax in C
• Confusing arrays with functions
• Omitting return type in function declaration

3. Consider the following C code snippet for a backtracking approach to find subsets of {1, 2}:

void backtrack(int start, int n) {
    if (start == n) {
        printf("Reached end\n");
        return;
    }
    backtrack(start + 1, n);
    backtrack(start + 1, n);
}
int main() {
    backtrack(0, 2);
    return 0;
}

What will be the output when this code runs?

medium

A. Reached end\n

B. Reached end\nReached end\n

C. Reached end\nReached end\nReached end\nReached end\n

D. No output

Solution

1. Step 1: Trace recursive calls

   backtrack(0,2) calls backtrack(1,2) twice; each backtrack(1,2) calls backtrack(2,2) twice.

2. Step 2: Count base case hits

   backtrack(2,2) prints "Reached end"; it is called 4 times total (2 calls from each of 2 calls at start=1).

3. Final Answer:

   Reached end\nReached end\nReached end\nReached end\n -> Option C

4. Quick Check:

   4 base calls print output = A [OK]

Hint: Count recursive calls reaching base case carefully [OK]

Common Mistakes:

• Counting only one base case print
• Confusing number of recursive calls
• Ignoring duplicate calls in recursion

4. The following C code attempts to solve the subset sum problem using backtracking but has a bug:

void backtrack(int index, int sum, int target, int arr[], int n) {
    if (sum == target) {
        printf("Found subset\n");
        return;
    }
    if (index == n || sum > target) {
        return;
    }
    backtrack(index + 1, sum + arr[index], target, arr, n);
    backtrack(index + 1, sum, target, arr, n);
}
int main() {
    int arr[] = {2, 4, 6};
    backtrack(0, 0, 6, arr, 3);
    return 0;
}

What is the bug in this code?

medium

A. It does not print all subsets that sum to target

B. It does not check if sum exceeds target before recursion

C. It does not handle negative numbers in array

D. It does not stop recursion after finding one subset

Solution

1. Step 1: Analyze base case for sum == target

   When sum equals target, it prints but continues recursion because no stop condition after printing.

2. Step 2: Identify missing stop after success

   Function returns only from current call, but parent calls continue exploring other subsets.

3. Final Answer:

   It does not stop recursion after finding one subset -> Option D

4. Quick Check:

   Missing stop after success = B [OK]

Hint: Stop recursion immediately after finding a valid subset [OK]

Common Mistakes:

• Assuming printing once stops all recursion
• Ignoring need to return from all recursive calls
• Confusing sum checks with recursion control

5. You want to solve the problem of finding all combinations of coins that sum to a target amount. Why can't a greedy algorithm always solve this correctly, and how does backtracking help? Choose the best explanation.

hard

A. Greedy picks largest coins first which may miss combinations; backtracking tries all coin choices systematically

B. Greedy uses more memory; backtracking uses less memory

C. Greedy is slower than backtracking for coin problems

D. Backtracking only tries one coin at a time, greedy tries all

Solution

1. Step 1: Understand greedy approach limitation

   Greedy picks largest coin repeatedly, which can miss valid combinations with smaller coins.

2. Step 2: Understand backtracking advantage

   Backtracking tries all coin combinations by exploring all choices and backtracking on failures.

3. Final Answer:

   Greedy picks largest coins first which may miss combinations; backtracking tries all coin choices systematically -> Option A

4. Quick Check:

   Greedy misses combos; backtracking explores all = A [OK]

Hint: Greedy misses combos; backtracking explores all systematically [OK]

Common Mistakes:

• Assuming greedy always finds all solutions
• Confusing memory use with correctness
• Thinking backtracking is always slower without context