Backtracking Introduction

🔙 Backtracking in C++ – Easy Introduction

Backtracking ek recursive problem-solving technique hai jisme hum ek solution banate jaate hain step-by-step, aur galti hone par pichhe (backtrack) hote hain to try another path.

🔹 Simple Definition:

Backtracking = Try + Fail + Backtrack + Try Again

Jab kisi point par solution nahi banta, toh wapas pichhe jaake dusra option try karte hain.

🔁 Real-Life Example:

📦 Imagine tum ek maze (bhool-bhulaiyaa) me ho —

Agar koi raasta band hai, toh tum wapis pichhe jaake dusra raasta try karte ho.

Yahi concept programming me backtracking kehlata hai.

🔧 C++ Code Structure of Backtracking:


bool solve(state) {
    if(base_case) {
        // solution mil gaya
        return true;
    }

    for(all choices) {
        if(choice is valid) {
            make the choice;
            if(solve(next state)) return true;
            undo the choice;  // 🔙 Backtrack
        }
    }
    return false;
}

✅ Examples of Backtracking Problems:

Problem	Description
🔢 Subsets	Power set (2^n combinations)
🔁 Permutations	All orderings of elements
♟ N-Queens Problem	Place N queens on board
🧩 Sudoku Solver	Fill valid digits
📦 Rat in a Maze	Find path in maze
♟ Knight’s Tour	Chess-based movement puzzle
🔐 Word Search (Matrix)	Search word in grid

✅ Example: Generate All Subsets (Power Set)


void generateSubsets(int index, vector<int>& nums, vector<int>& subset) {
    if(index == nums.size()) {
        for(int val : subset) cout << val << " ";
        cout << endl;
        return;
    }

    // Not take current element
    generateSubsets(index + 1, nums, subset);

    // Take current element
    subset.push_back(nums[index]);
    generateSubsets(index + 1, nums, subset);
    subset.pop_back(); // 🔙 backtrack
}

📌 subset.pop_back() = backtracking step