Backtracking Concept and Decision Tree Visualization in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Path Exploration

What is the output of the following C code that uses backtracking to print all subsets of {1, 2}?

DSA C

#include <stdio.h>
void backtrack(int arr[], int n, int index, int subset[], int subset_size) {
    if (index == n) {
        printf("{");
        for (int i = 0; i < subset_size; i++) {
            printf("%d", subset[i]);
            if (i < subset_size - 1) printf(", ");
        }
        printf("}\n");
        return;
    }
    // Include current element
    subset[subset_size] = arr[index];
    backtrack(arr, n, index + 1, subset, subset_size + 1);
    // Exclude current element
    backtrack(arr, n, index + 1, subset, subset_size);
}
int main() {
    int arr[] = {1, 2};
    int subset[2];
    backtrack(arr, 2, 0, subset, 0);
    return 0;
}

A

{}
{1}
{2}
{1, 2}

B

{}
{2}
{1}
{1, 2}

C

{1}
{1, 2}
{2}
{}

D

{1, 2}
{1}
{2}
{}

💡 Hint

Think about the order in which the backtracking includes and excludes elements.

The backtracking first explores the path excluding all elements, printing the empty set {}. Then it includes elements in order, printing {1}, {2}, and finally {1, 2}.

🧠 Conceptual

intermediate

Number of Nodes in Backtracking Decision Tree

For a backtracking algorithm that explores all subsets of a set with 3 elements, how many nodes are there in the decision tree?

A 8

B 15

C 16

D 7

💡 Hint

Each element can be either included or excluded, forming a binary tree.

For 3 elements, the decision tree is a full binary tree with height 3. It has 2^(3+1) - 1 = 15 nodes.

🔧 Debug

advanced

Identify the Backtracking Logic Error

What error does the following C code produce when trying to generate permutations of {1, 2}?

DSA C

#include <stdio.h>
void permute(int arr[], int start, int end) {
    if (start == end) {
        for (int i = 0; i <= end; i++) printf("%d ", arr[i]);
        printf("\n");
    } else {
        for (int i = start; i <= end; i++) {
            int temp = arr[start];
            arr[start] = arr[i];
            arr[i] = temp;
            permute(arr, start + 1, end);
            // Missing swap back here
        }
    }
}
int main() {
    int arr[] = {1, 2};
    permute(arr, 0, 1);
    return 0;
}

A Compilation error due to missing semicolon

B Causes infinite recursion

C Prints no output

D Prints duplicate permutations

💡 Hint

Check if the array is restored after recursive calls.

The code swaps elements but does not swap them back after recursion, causing the array to remain changed and producing duplicate permutations.

❓ Predict Output

advanced

Output of Backtracking with Pruning

What is the output of this C code that uses backtracking with pruning to find subsets of {1, 2, 3} with sum less than 4?

DSA C

#include <stdio.h>
void backtrack(int arr[], int n, int index, int subset[], int subset_size, int current_sum) {
    if (current_sum >= 4) return;
    if (index == n) {
        printf("{");
        for (int i = 0; i < subset_size; i++) {
            printf("%d", subset[i]);
            if (i < subset_size - 1) printf(", ");
        }
        printf("}\n");
        return;
    }
    // Include current element
    subset[subset_size] = arr[index];
    backtrack(arr, n, index + 1, subset, subset_size + 1, current_sum + arr[index]);
    // Exclude current element
    backtrack(arr, n, index + 1, subset, subset_size, current_sum);
}
int main() {
    int arr[] = {1, 2, 3};
    int subset[3];
    backtrack(arr, 3, 0, subset, 0, 0);
    return 0;
}

A

{}
{3}
{2}
{2, 3}
{1}
{1, 3}
{1, 2}
{1, 2, 3}

B

{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}

C

{}
{1}
{2}
{3}
{1, 2}
{1, 3}

D

{}
{1}
{2}
{1, 2}
{3}

💡 Hint

Subsets with sum 4 or more are skipped.

Subsets like {2, 3} and {1, 2, 3} have sums 5 and 6 respectively, so they are pruned and not printed.

🧠 Conceptual

expert

Backtracking Tree Height and Leaf Count

In a backtracking algorithm generating all permutations of n distinct elements, what is the height of the decision tree and how many leaf nodes does it have?

A Height = n, Leaf nodes = n!

B Height = n!, Leaf nodes = n

C Height = n-1, Leaf nodes = n^2

D Height = 2^n, Leaf nodes = 2^n

💡 Hint

Each level fixes one element in the permutation.

The decision tree height equals the number of elements n, and the leaf nodes represent all permutations, which are n!.

Practice

1. What is the main idea behind the backtracking technique in algorithms?

easy

A. Divide the problem into smaller independent parts

B. Sort the data before processing

C. Try all possible options and undo choices when they lead to no solution

D. Use a queue to process elements in order

Solution

1. Step 1: Understand backtracking approach

   Backtracking tries all possible options step-by-step and undoes choices if they don't lead to a solution.

2. Step 2: Compare with other options

   Sorting, queues, and dividing problems are different techniques, not backtracking.

3. Final Answer:

   Try all possible options and undo choices when they lead to no solution -> Option C

4. Quick Check:

   Backtracking = Try and undo choices [OK]

Hint: Backtracking means try, check, and undo if needed [OK]

Common Mistakes:

• Confusing backtracking with sorting or divide and conquer
• Thinking backtracking only tries one path
• Ignoring the undo step in backtracking

2. Which of the following is the correct syntax to start a backtracking function in C that takes an integer step as input?

easy

A. void backtrack(int step) { }

B. int backtrack() { step; }

C. backtrack(int step) void { }

D. void backtrack step(int) { }

Solution

1. Step 1: Recall C function syntax

   In C, a function with no return value uses void, name, and parameters in parentheses.

2. Step 2: Check each option

   void backtrack(int step) { } matches correct syntax: void backtrack(int step) { }. Others have wrong order or missing parts.

3. Final Answer:

   void backtrack(int step) { } -> Option A

4. Quick Check:

   Correct C function syntax = void backtrack(int step) { } [OK]

Hint: C functions: return_type name(params) { } [OK]

Common Mistakes:

• Placing parameter type after name incorrectly
• Missing parentheses around parameters
• Wrong order of return type and function name

3. Consider the following C code snippet for backtracking to generate binary strings of length 2:

void backtrack(int step, char *arr) {
  if (step == 2) {
    printf("%s\n", arr);
    return;
  }
  arr[step] = '0';
  backtrack(step + 1, arr);
  arr[step] = '1';
  backtrack(step + 1, arr);
}

int main() {
  char arr[3] = {0};
  backtrack(0, arr);
  return 0;
}

What is the output of this program?

medium

A. 0
1
0
1

B. 00
01
10
11

C. 00
11

D. Syntax error

Solution

1. Step 1: Understand recursion and base case

   When step == 2, the string is printed. The array holds characters '0' or '1' at each step.

2. Step 2: Trace recursive calls

   At step 0: arr[0] = '0', recurse; then arr[0] = '1', recurse. At step 1: arr[1] = '0', recurse; then arr[1] = '1', recurse. This generates all 2-length binary strings.

3. Final Answer:

   00 01 10 11 -> Option B

4. Quick Check:

   All 2-length binary strings printed [OK]

Hint: Backtracking prints all combos by changing one position at a time [OK]

Common Mistakes:

• Not setting null terminator for string
• Printing before base case reached
• Confusing step count with array length

4. The following backtracking code is intended to generate all permutations of the array {1, 2}. What is the error?

void backtrack(int *arr, int start, int end) {
  if (start == end) {
    for (int i = 0; i <= end; i++) printf("%d", arr[i]);
    printf("\n");
    return;
  }
  for (int i = start; i <= end; i++) {
    int temp = arr[start];
    arr[start] = arr[i];
    arr[i] = temp;
    backtrack(arr, start + 1, end);
    // Missing swap back here
  }
}

int main() {
  int arr[] = {1, 2};
  backtrack(arr, 0, 1);
  return 0;
}

medium

A. The base case condition is incorrect

B. The array is not initialized properly

C. The loop should run from 0 to end, not start to end

D. The code misses swapping back after recursion, causing wrong output

Solution

1. Step 1: Analyze swapping logic

   The code swaps elements before recursion but does not swap them back after recursion, so the array stays changed incorrectly.

2. Step 2: Understand effect on output

   Without swapping back, permutations are not generated correctly because the original order is lost.

3. Final Answer:

   The code misses swapping back after recursion, causing wrong output -> Option D

4. Quick Check:

   Swap back needed to restore array [OK]

Hint: Always undo swaps after recursive calls in permutations [OK]

Common Mistakes:

• Forgetting to swap back after recursion
• Wrong loop range for permutations
• Incorrect base case check

5. You want to use backtracking to solve the N-Queens problem for N=4. Which of the following best describes the decision tree visualization for this problem?

hard

A. A tree where each level represents placing a queen in a row, branching by valid columns

B. A tree where each node represents a queen placed anywhere on the board without restrictions

C. A linear chain of nodes representing queens placed one after another without backtracking

D. A tree where each level represents removing queens from the board

Solution

1. Step 1: Understand N-Queens backtracking

   Backtracking places queens row by row, trying valid columns only to avoid attacks.

2. Step 2: Visualize decision tree

   Each tree level corresponds to a row; branches represent valid column choices for that queen.

3. Final Answer:

   A tree where each level represents placing a queen in a row, branching by valid columns -> Option A

4. Quick Check:

   Decision tree levels = rows, branches = valid columns [OK]

Hint: Decision tree levels = rows, branches = valid queen positions [OK]

Common Mistakes:

• Ignoring constraints when placing queens
• Thinking decision tree is linear without branches
• Confusing placement with removal steps