Why Backtracking and What Greedy Cannot Solve in DSA C - See It Work

Why Backtracking and What Greedy Cannot Solve

📖 Scenario: Imagine you are organizing a small party and want to invite friends. Each friend has a different preference for who else should be invited. You want to find all possible groups of friends that can come together without conflicts.This is a real-life example where simple greedy choices won't work because inviting one friend might block others. Instead, you need to try different combinations carefully.

🎯 Goal: Build a simple program that tries all possible groups of friends using backtracking to find valid groups. Understand why greedy methods fail here and how backtracking explores all options.

📋 What You'll Learn

Create an array of friends with their conflict information

Use a helper variable to track the current group size

Implement backtracking to find all valid groups without conflicts

Print each valid group found

💡 Why This Matters

🌍 Real World

Backtracking helps solve problems like scheduling, puzzles, and group selection where choices affect each other.

💼 Career

Understanding backtracking is important for software roles involving algorithms, optimization, and problem solving.

1

Create the friends conflict matrix

Create a 2D integer array called conflict of size 4x4 with these exact values: {{0, 1, 0, 0}, {1, 0, 1, 0}, {0, 1, 0, 1}, {0, 0, 1, 0}}. This matrix shows which friends conflict with each other.

DSA C

# Your code here

Hint

This matrix shows which friends cannot be invited together. For example, friend 0 conflicts with friend 1.

2

Add a variable to track current group size

Add an integer variable called group_size and set it to 0. This will track how many friends are currently invited.

DSA C

int conflict[4][4] = {
    {0, 1, 0, 0},
    {1, 0, 1, 0},
    {0, 1, 0, 1},
    {0, 0, 1, 0}
};

# Your code here

Hint

This variable helps keep count of how many friends you have invited so far.

3

Implement backtracking to find valid groups

Write a function called backtrack that takes an integer friend_index and an integer array group. Use backtracking to try inviting or skipping each friend from friend_index to 3. Only add a friend if they do not conflict with anyone already in group. Update group_size accordingly.

DSA C

int conflict[4][4] = {
    {0, 1, 0, 0},
    {1, 0, 1, 0},
    {0, 1, 0, 1},
    {0, 0, 1, 0}
};

int group_size = 0;

// Your code here to write backtrack function

Hint

Use recursion to try both inviting and skipping each friend. Check conflicts before inviting.

4

Print all valid groups using backtracking

In the main function, call backtrack(0) to start finding all valid groups from friend 0. Then return 0.

DSA C

int conflict[4][4] = {
    {0, 1, 0, 0},
    {1, 0, 1, 0},
    {0, 1, 0, 1},
    {0, 0, 1, 0}
};

int group_size = 0;

#include 

int group[4];

int can_invite(int friend_index) {
    for (int i = 0; i  0) {
            print_group();
        }
        return;
    }

    // Try skipping this friend
    backtrack(friend_index + 1);

    // Try inviting this friend if no conflict
    if (can_invite(friend_index)) {
        group[group_size] = friend_index;
        group_size++;
        backtrack(friend_index + 1);
        group_size--;
    }
}

// Your code here to call backtrack in main

Hint

Call backtrack(0) inside main to start the search and print all valid groups.