Backtracking

Backtracking Algorithms in C++

A comprehensive guide to backtracking algorithms with code implementations and problem-solving patterns.

Table of Contents

1. Basic Recursion Problems
2. Subsequence Generation
3. Permutation Problems
4. Combination Problems
5. Constraint Satisfaction Problems
6. Sorting Algorithms
7. Path Finding Problems

---

Basic Recursion Problems

1. Print Numbers 1 to N

Problem: Print numbers from 1 to N using recursion Pattern: Simple recursion with base case

#include<iostream>
using namespace std;
void f(int n){
    if(n==0) return;
    f(n-1);
    cout<<n<<" ";
}
int main(){
    int n;
    cin>>n;
    f(n);
}

Logic:

• Base case: n == 0
• Recursive call first, then print (ensures ascending order)
• Time Complexity: O(n), Space Complexity: O(n)

2. Fibonacci Series

Problem: Calculate nth Fibonacci number Pattern: Multiple recursive calls

#include<iostream>
using namespace std;
int fibonaki(int n){
    if(n<=1){
        return n;
    }
    return fibonaki(n-1)+fibonaki(n-2);
}
int main(){
    int n;
    cin>>n;
    cout<<fibonaki(n);
}

Logic:

• Base cases: f(0)=0, f(1)=1
• Recurrence: f(n) = f(n-1) + f(n-2)
• Time Complexity: O(2^n), Space Complexity: O(n)

3. Sum of N Numbers

Problem: Calculate sum of numbers from 1 to N Pattern: Accumulator recursion

#include<iostream>
using namespace std;
int sum(int n){
    if(n==0)
        return 0;
    return n+sum(n-1);
}
int main(){
    int n;
    cin>>n;
    cout<<sum(n);
    return 0;
}

Logic:

• Base case: sum(0) = 0
• Recurrence: sum(n) = n + sum(n-1)
• Time Complexity: O(n), Space Complexity: O(n)

4. Array Reversal

Problem: Reverse an array using recursion Pattern: Two-pointer recursion

#include<iostream>
#include<vector>

void f(std::vector<int> &arr,int i,int j){
    if(i>=j){
        return;
    }
    std::swap(arr[i],arr[j]);
    f(arr,i+1,j-1);
}
void reverse(std::vector<int> &arr){
    int n=arr.size();
    f(arr,0,n-1);
}
int main(){
    std::vector<int> arr={1,2,3,4,5};
    reverse(arr);
    for(auto i:arr){
        std::cout<<i<<" ";
    }
}

Logic:

• Two pointers: start and end
• Swap elements and move pointers inward
• Base case: pointers meet or cross
• Time Complexity: O(n), Space Complexity: O(n)

5. Palindrome Check

Problem: Check if string is palindrome using recursion Pattern: Two-pointer comparison

#include<iostream>
#include<string>
using namespace std;
bool isPalandrom(string s,int i,int j){
    if(i>=j){
        return true;
    }
    if(s[i]!=s[j]){
        return false;
    }
    return isPalandrom(s,i+1,j-1);
}
int main(){
    string s="abba";
    cout<<isPalandrom(s,0,s.size()-1);
}

Logic:

• Compare characters from both ends
• If mismatch found, return false
• If all characters match, return true
• Time Complexity: O(n), Space Complexity: O(n)

---

Subsequence Generation

6. Generate All Subsequences

Problem: Generate all possible subsequences of an array Pattern: Pick/Not Pick recursion

#include<iostream>
#include<vector>
std::vector<int> temp;
void f(std::vector<int> &arr,int i){
    if(i==arr.size()){
        for(int i:temp) std::cout<<i<<" ";
        std::cout<<"\n";
        return;
    }
    temp.push_back(arr[i]);
    f(arr,i+1);
    temp.pop_back();
    f(arr, i+1);
}
int main(){
    std::vector<int> arr = {1,2,3};
    f(arr, 0);
    return 0;
}

Logic:

• For each element: include it or exclude it
• Two recursive calls: with and without current element
• Time Complexity: O(2^n), Space Complexity: O(n)

7. Subsequences with Sum K

Problem: Find all subsequences with sum equal to K Pattern: Pick/Not Pick with constraint

#include<bits/stdc++.h>
using namespace std;
int k=4;
void f(int i,vector<int> arr,vector<int> &dp){
    if(i==arr.size()){
        int sum=accumulate(dp.begin(),dp.end(),0);
        if(sum==k){
            for(int i:dp){
                cout<<i<<" ";
            }
            cout<<endl;
        }
        return;
    }
    dp.push_back(arr[i]);
    f(i+1,arr,dp);
    dp.pop_back();
    f(i+1,arr,dp);
}
int main(){
    vector<int> arr={1,2,3,4};
    vector<int> dp;
    f(0,arr,dp);
    return 0;
}

Logic:

• Same pick/not pick pattern
• Check sum at base case
• Print only if sum equals target
• Time Complexity: O(2^n), Space Complexity: O(n)

8. Count Subsequences with Sum K

Problem: Count number of subsequences with sum K Pattern: Pick/Not Pick with counting

#include<bits/stdc++.h>
using namespace std;
int k=4;
int f(int i,vector<int> arr,vector<int> &res){
    if(i==arr.size()){
        int sum=accumulate(res.begin(),res.end(),0);
        if(sum==k){
            return 1;
        }
        return 0;
    }
    res.push_back(arr[i]);
    int l=f(i+1,arr,res);
    res.pop_back();
    int r=f(i+1,arr,res);
    return l+r;
}
int main(){
    vector<int> arr={1,2,3,4};
    vector<int> res;
    cout<<f(0,arr,res);
    return 0;
}

Logic:

• Return 1 if sum matches, 0 otherwise
• Add results from both recursive calls
• Time Complexity: O(2^n), Space Complexity: O(n)

9. Find First Subsequence with Sum K

Problem: Find first subsequence with sum K and stop Pattern: Pick/Not Pick with early termination

#include<bits/stdc++.h>
using namespace std;
int k=4;
bool f(int i,vector<int> arr,vector<int> &dp){
    if(i==arr.size()){
        int sum=accumulate(dp.begin(),dp.end(),0);
        if(sum==k){
            for(int i:dp){
                cout<<i<<" ";
            }
            cout<<endl;
            return true;
        }
        return false;
    }
    dp.push_back(arr[i]);
    if(f(i+1,arr,dp)) return true;
    dp.pop_back();
    if(f(i+1,arr,dp)) return true;
    return false;
}
int main(){
    vector<int> arr={1,2,3,4};
    vector<int> dp;
    f(0,arr,dp);
    return 0;
}

Logic:

• Return true when first valid subsequence found
• Early termination prevents exploring other branches
• Time Complexity: O(2^n) worst case, Space Complexity: O(n)

---

Permutation Problems

10. All String Permutations

Problem: Generate all permutations of a string Pattern: Fix one character, permute rest

#include<bits/stdc++.h>

void allcombination(std::string str,std::string dp,std::unordered_set<int> &s){
    if(dp.size() == str.size()){
        std::cout<<dp<<std::endl;
        return;
    }
    for(int i=0;i<str.size();i++){
        if(s.find(i)==s.end()){
            s.insert(i);
            allcombination(str, dp+str[i], s);
            s.erase(i);
        }
    }
}
int main(){
    std::string str = "abc";
    std::unordered_set<int> s;
    allcombination(str, "", s);
    return 0;
}

Logic:

• Use set to track used characters
• Try each unused character at current position
• Backtrack by removing from set
• Time Complexity: O(n!), Space Complexity: O(n)

11. All Array Permutations

Problem: Generate all permutations of an array Pattern: Frequency array for tracking used elements

#include<bits/stdc++.h>

std::vector<std::vector<int>> ans;
void allArrayCombination(std::vector<int> &arr,std::vector<int> &freq,std::vector<int> &dp){
    if(arr.size()==dp.size()){
        ans.push_back(dp);
        return;
    }
    for(int i=0;i<arr.size();i++){
        if(!freq[i]){
            freq[i]=true;
            dp.push_back(arr[i]);
            allArrayCombination(arr,freq,dp);
            dp.pop_back();
            freq[i]=false;
        }
    }
}
int main(){
    std::vector<int> arr={1,2,3};
    std::vector<int> freq(arr.size(), false);
    std::vector<int> dp;
    allArrayCombination(arr, freq, dp);
    for(auto i:ans){
        for(auto j:i){
            std::cout<<j<<" ";
        }
        std::cout<<std::endl;
    }
    return 0;
}

Logic:

• Frequency array tracks which elements are used
• Try each unused element at current position
• Backtrack by marking element as unused
• Time Complexity: O(n!), Space Complexity: O(n)

---

Combination Problems

12. Combination Sum with Repetition

Problem: Find all combinations that sum to target (elements can be reused) Pattern: Include current element multiple times or skip

#include<bits/stdc++.h>

std::vector<std::vector<int>> result;
void findallcombination(std::vector<int> &arr,int i,std::vector<int> &dp,int k){
    int sum=std::accumulate(dp.begin(),dp.end(),0);
    if (i>=arr.size()||sum>=k){
        if(sum==k) result.push_back(dp);
        return;
    }
    dp.push_back(arr[i]);
    findallcombination(arr,i,dp,k);
    dp.pop_back();
    findallcombination(arr,i+1,dp,k);
}
int main(){
    std::vector<int> arr={1,2,3,4,5};
    int k=5;
    std::vector<int> dp;
    findallcombination(arr, 0, dp, k);
    for(auto i:result){
        for(auto j:i){
            std::cout<<j<<" ";
        }
        std::cout<<std::endl;
    }
    return 0;
}

Logic:

• Two choices: include current element again or move to next
• Early termination when sum exceeds target
• Time Complexity: Exponential, Space Complexity: O(target/min_element)

13. Unique Combinations

Problem: Generate all unique combinations from array with duplicates Pattern: Skip duplicates at same recursion level

#include<bits/stdc++.h>

std::vector<std::vector<int>> ans;
void unique(int ind,std::vector<int> &arr,std ::vector<int> &dp){
    if(ind==arr.size()){
        ans.push_back(dp);
    };
    
    for(int i=ind;i<arr.size();i++){
        if(i!=ind&&arr[i]==arr[i-1]) continue;
        dp.push_back(arr[i]);
        unique(i+1,arr,dp);
        dp.pop_back();
    }
}
int main(){
    std::vector<int> arr={1,1,1,2,3,3};
    std::vector<int> dp;
    unique(0, arr, dp);
    for(auto i: ans){
        for(auto j: i){
            std::cout<<j<<" ";
        }
        std::cout<<std::endl;
    }
    return 0;
}

Logic:

• Sort array first to group duplicates
• Skip duplicates at same recursion level
• Include each unique element once per level
• Time Complexity: O(2^n), Space Complexity: O(n)

---

Constraint Satisfaction Problems

14. N-Queens Problem

Problem: Place N queens on N×N chessboard such that no two queens attack each other Pattern: Constraint satisfaction with backtracking

#include<bits/stdc++.h>

int n=4;
std::vector<std::vector<std::vector<char>>> res;
std::vector<int> rowCheck(n,0),upperD(2*n-1,0),lowerD(2*n-1,0);

void Dnquene(int col,std::vector<std::vector<char>> &board){
    if(col==board.size()){
        res.push_back(board);
        return;
    }
    for(int row=0;row<board.size();row++){
        if(rowCheck[row]==0&&upperD[row+col]==0&&lowerD[board.size()-1+col-row]==0){
            lowerD[board.size()-1+col-row]=1;
            upperD[row+col]=1;
            rowCheck[row]=1;
            board[row][col]='Q';
            Dnquene(col+1,board);
            board[row][col]='.';
            rowCheck[row]=0;
            upperD[row+col]=0;
            lowerD[board.size()-1+col-row]=0;
        }
    }
}
int main(){
    std::vector<std::vector<char>> board(n,std::vector<char>(n,'.'));
    Dnquene(0,board);
    for(auto i:res){
        for(auto j:i){
            for(auto k:j){
                std::cout<<k<<" ";
            }
            std::cout<<std::endl;
        }
        std::cout<<std::endl;
    }
    return 0;
}

Logic:

• Place queens column by column
• Check row, upper diagonal, lower diagonal constraints
• Use arrays to track attacked positions efficiently
• Time Complexity: O(n!), Space Complexity: O(n)

15. Sudoku Solver

Problem: Solve 9×9 Sudoku puzzle Pattern: Constraint satisfaction with validation

#include<bits/stdc++.h>

bool isValid(std::vector<std::vector<char>> &sudoko,int row,int col,char ch){
    for(int i=0;i<9;i++){
        if(sudoko[row][i]==ch) return false;
        if(sudoko[i][col]==ch) return false;
        if(sudoko[3*(row/3)+i/3][3*(col/3)+i%3]==ch) return false;
    }
    return true;
}
bool solve(std::vector<std::vector<char>> &sudoko){
    for(int i=0;i<sudoko.size();i++){
        for(int j=0;j<sudoko[0].size();j++){
            if(sudoko[i][j]=='.'){
                for(char ch='1';ch<='9';ch++){
                    if(isValid(sudoko,i,j,ch)){
                        sudoko[i][j]=ch;
                        if(solve(sudoko)==true) return true;
                        else sudoko[i][j]='.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}

Logic:

• Find empty cell, try digits 1-9
• Check row, column, and 3×3 box constraints
• Backtrack if no valid digit found
• Time Complexity: O(9^(nn)), Space Complexity: O(nn)

16. Graph Coloring

Problem: Color graph vertices with minimum colors such that no adjacent vertices have same color Pattern: Constraint satisfaction with adjacency check

#include<bits/stdc++.h>

int n;
std::unordered_map<int,std::unordered_set<int>> graph;
std::vector<int> color;
bool isSafe(int node,std::unordered_map<int,std::unordered_set<int>> &graph,int col){
    for(int i:graph[node]){
        if(color[i]==col) return false;
    }
    return true;
}
bool solve(int node,std::unordered_map<int,std::unordered_set<int>> &graph,int M){
    if(node==n) return true;
    for(int i=0;i<M;i++){
        if(isSafe(node,graph,i)){
            color[node]=i;
            if (solve(node+1,graph,M)==true) return true;
            color[node]=-1;
        }
    }
    return false;
}

Logic:

• Try each color for current vertex
• Check if color conflicts with adjacent vertices
• Backtrack if no valid color found
• Time Complexity: O(M^n), Space Complexity: O(n)

---

Sorting Algorithms

17. Merge Sort

Problem: Sort array using divide and conquer Pattern: Divide, solve recursively, merge

#include<bits/stdc++.h>

void merge(std::vector<int> &arr,int i,int m,int j){
    std::vector<int> temp;
    int l=i,r=m+1;
    while(l<=m&&r<=j){
        if(arr[l]<arr[r]){
            temp.push_back(arr[l++]);
        }else{
            temp.push_back(arr[r++]);
        }
    }
    while(l<=m) temp.push_back(arr[l++]);
    while(r<=j) temp.push_back(arr[r++]);
    l=0;
    for(int k=i;k<=j;k++){
        arr[k]=temp[l++];
    }
    return;
}

void mergesort(std::vector<int> &arr,int i,int j){
    if(i>=j) return;
    int m=i+(j-i)/2;
    mergesort(arr,i,m);
    mergesort(arr,m+1,j);
    merge(arr,i,m,j);
}

Logic:

• Divide array into two halves
• Recursively sort both halves
• Merge sorted halves
• Time Complexity: O(n log n), Space Complexity: O(n)

18. Quick Sort

Problem: Sort array using pivot partitioning Pattern: Partition around pivot, recursively sort

#include<bits/stdc++.h>

int partion(std::vector<int> &arr,int i,int j){
    int l=i;
    i+=1;
    while(i<j){
        while(arr[i]<arr[l]) i++;
        while(arr[j]>arr[l]) j--;
        if(i<j){
            std::swap(arr[i],arr[j]);
            i++;
            j--;
        }
    }
    std::swap(arr[j],arr[l]);
    return j;
}
void quicksort(std::vector<int> &arr,int low,int high){
    if(low<high){
        int piv=partion(arr,low,high);
        quicksort(arr,low,piv-1);
        quicksort(arr,piv+1,high);
    }
}

Logic:

• Choose pivot, partition array around it
• Recursively sort left and right subarrays
• In-place sorting algorithm
• Time Complexity: O(n log n) average, O(n²) worst, Space Complexity: O(log n)

---

Path Finding Problems

19. Rat in Maze

Problem: Find all paths from top-left to bottom-right in maze Pattern: 4-directional DFS with backtracking

#include<bits/stdc++.h>

std::vector<std::vector<int>> maze;
std::vector<std::vector<std::vector<int>>> ans;
int n,m;
int count=0;
void findlastCombination(std::vector<std::vector<int>> &maze,int i,int j){
    if(i==n-1&&j==m-1){
        count++;
        ans.push_back(maze);
        return;
    }
    if((i+1)<n&&maze[i+1][j]==0){
        maze[i+1][j]=8;
        findlastCombination(maze,i+1,j);
        maze[i+1][j]=0;
    }
    if((j-1)>=0&&maze[i][j-1]==0){
        maze[i][j-1]=8;
        findlastCombination(maze,i,j-1);
        maze[i][j-1]=0;
    }
    if((j+1)<m&&maze[i][j+1]==0){
        maze[i][j+1]=8;
        findlastCombination(maze,i,j+1);
        maze[i][j+1]=0;
    }
    if((i-1)>=0&&maze[i-1][j]==0){
        maze[i-1][j]=8;
        findlastCombination(maze,i-1,j);
        maze[i-1][j]=0;
    }
}

Logic:

• Explore all 4 directions (up, down, left, right)
• Mark visited cells, backtrack after exploring
• Count all possible paths to destination
• Time Complexity: O(4^(mn)), Space Complexity: O(mn)

---

Key Backtracking Patterns Summary

1. Decision Tree Pattern

• Each recursive call represents a decision point
• Explore all possible decisions
• Backtrack when constraint violated or solution found

2. State Space Search

• Define state representation
• Define valid state transitions
• Implement constraint checking

3. Optimization Techniques

• Pruning: Skip branches that can't lead to solution
• Early Termination: Stop when first solution found
• Constraint Propagation: Use constraints to reduce search space

4. Common Templates

Subset Generation Template:

void backtrack(int index, vector<int>& current) {
    if (index == n) {
        // Process current subset
        return;
    }
    // Include current element
    current.push_back(arr[index]);
    backtrack(index + 1, current);
    current.pop_back();
    
    // Exclude current element
    backtrack(index + 1, current);
}

Permutation Template:

void backtrack(vector<int>& current, vector<bool>& used) {
    if (current.size() == n) {
        // Process current permutation
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = true;
            current.push_back(arr[i]);
            backtrack(current, used);
            current.pop_back();
            used[i] = false;
        }
    }
}

Constraint Satisfaction Template:

bool backtrack(int position) {
    if (position == target) {
        return true; // Solution found
    }
    for (each possible value) {
        if (isValid(position, value)) {
            assign(position, value);
            if (backtrack(position + 1)) {
                return true;
            }
            unassign(position, value);
        }
    }
    return false; // No solution found
}

This comprehensive guide covers all major backtracking patterns with working code examples and detailed explanations of the logic behind each approach.