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!.