Mastering DFS Algorithms: Complete Training Guide with Problem-Solving Templates

Depth-First Search (DFS) represents one of the most fundamental and versatile algorithms in computer science. This comprehensive training guide covers essential DFS patterns, templates, and problem-solving strategies drawn from extensive competitive programming experience. Whether you're preparing for coding interviews, participating in programming contests, or simply strengthening your algorithmic foundation, this guide provides the practical knowledge you need.

Understanding Memory Limits in Competitive Programming

Before diving into DFS implementations, it's crucial to understand memory constraints, especially when working with multi-dimensional arrays:

Integer Arrays (int)

• 256MB memory limit = 256 × 1024 × 1024 bytes ≈ 67 million integers
• 3000×3000 int array: 36MB ✅ Safe
• 4000×4000 int array: 64MB ✅ Safe
• 5000×5000 int array: 100MB ✅ Safe
• 8000×8000 int array: 256MB ❌ At the limit

For competitive programming platforms like Lanqiao, global int arrays up to 5000×5000 are generally safe. In actual competitions, staying within 3000×3000 is recommended for stability.

Boolean Arrays (bool)

• 16000×16000 bool array: 256MB ❌ At the limit
• 10000×10000 bool array: 100MB ✅ Safe
• 5000×5000 bool array: 25MB ✅ Very safe

Core DFS Template: Permutations

Problem Statement

Generate all permutations of numbers from 1 to n.

Sample Input:

3

Sample Output:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Recursive Implementation

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;
int a[N], b[N];  // a stores current permutation, b tracks used numbers
int n;

void dfs(int x) {
    if (x == n + 1) {  // Base case: all positions filled
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
        return;
    }
    
    for (int i = 1; i <= n; i++) {
        if (b[i] == 0) {  // If number i hasn't been used
            b[i] = 1;      // Mark as used
            a[x] = i;      // Place in current position
            dfs(x + 1);    // Recurse to next position
            a[x] = 0;      // Backtrack
            b[i] = 0;      // Unmark for other permutations
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    dfs(1);
    return 0;
}

Alternative: Using next_permutation

Method 1: Manual iteration

#include <bits/stdc++.h>
using namespace std;

int n, a[100];

int main() {
    scanf("%d", &n);
    int tot = 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = i;
        tot *= i;  // Calculate n!
    }
    
    for (int i = 1; i <= tot; ++i) {
        for (int j = 1; j <= n; ++j)
            printf("%d ", a[j]);
        next_permutation(a + 1, a + n + 1);
        printf("\n");
    }
    return 0;
}

Method 2: do-while loop

#include<bits/stdc++.h>
using namespace std;

int n, a[100];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    
    for (int i = 1; i <= n; i++)
        a[i] = i;
    
    do {
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    } while (next_permutation(a + 1, a + n + 1));
    
    return 0;
}

Select or Not Select Pattern

This fundamental pattern forms the basis for many subset and combination problems:

#include<bits/stdc++.h>
using namespace std;

int n;           // Number of items
int a[25];       // Item values/weights
bool vis[25];    // Selection tracking (optional)
int ans;         // Result storage

// Core DFS template
// k: current item being considered
// current_sum: accumulated state (sum, weight, value, etc.)
void dfs(int k, int current_sum) {
    if (k > n) {  // All items processed
        // Handle final answer here
        // Update max/min, count solutions, output solution, etc.
        ans = max(ans, current_sum);
        return;
    }
    
    // Choice 1: Don't select item k
    vis[k] = false;
    dfs(k + 1, current_sum);
    
    // Choice 2: Select item k
    vis[k] = true;
    dfs(k + 1, current_sum + a[k]);
    // Note: If vis is global, may need to backtrack: vis[k] = false;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    dfs(1, 0);  // Start from item 1, initial state 0
    return 0;
}

Common Variations

1. Count Subsets with Sum Equal to Target

void dfs(int k, int sum) {
    if (k > n) {
        if (sum == target)
            ans++;
        return;
    }
    dfs(k + 1, sum);              // Don't select
    dfs(k + 1, sum + a[k]);       // Select
}

2. Find Max/Min Sum When Selecting k Numbers

void dfs(int pos, int cnt, int sum) {
    // cnt: number of items selected so far
    if (cnt > k) return;          // Pruning: selected too many
    
    if (pos > n) {
        if (cnt == k)
            ans = max(ans, sum);
        return;
    }
    
    dfs(pos + 1, cnt + 1, sum + a[pos]);  // Select
    dfs(pos + 1, cnt, sum);                // Don't select
}

3. Record Specific Solutions (Backtracking)

vector<int> path;

void dfs(int k, int sum) {
    if (k > n) {
        if (sum == target) {
            for (int x : path)
                cout << x << " ";
            cout << endl;
        }
        return;
    }
    
    // Don't select
    dfs(k + 1, sum);
    
    // Select
    path.push_back(a[k]);
    dfs(k + 1, sum + a[k]);
    path.pop_back();  // Backtrack
}

4. Weight-Constrained Problems (Knapsack-style)

void dfs(int k, int weight, int value) {
    if (weight > W) return;  // Pruning: exceeded weight limit
    
    if (k > n) {
        ans = max(ans, value);
        return;
    }
    
    dfs(k + 1, weight, value);                    // Don't select
    dfs(k + 1, weight + w[k], value + v[k]);     // Select
}

BFS Template: Shortest Path (Maze Problems)

While this guide focuses on DFS, understanding BFS is equally important for shortest path problems:

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int n, m;                     // Map dimensions
char g[N][N];                 // Map: '.' = empty, '#' = obstacle
int dist[N][N];               // Distance array, -1 = unvisited
int dx[4] = {-1, 0, 1, 0};    // Four directions: up, right, down, left
int dy[4] = {0, 1, 0, -1};

int bfs(int sx, int sy, int ex, int ey) {
    memset(dist, -1, sizeof dist);
    queue<pair<int, int>> q;
    
    dist[sx][sy] = 0;         // Starting point distance = 0
    q.push({sx, sy});
    
    while (q.size()) {
        auto t = q.front();
        q.pop();
        
        int x = t.first, y = t.second;
        
        if (x == ex && y == ey)  // Reached destination
            return dist[x][y];
        
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            
            // Boundary check + obstacle check + visited check
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (g[a][b] == '#') continue;
            if (dist[a][b] != -1) continue;
            
            dist[a][b] = dist[x][y] + 1;
            q.push({a, b});
        }
    }
    
    return -1;  // Cannot reach destination
}

DFS Template: Connected Components (Flood Fill)

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
char g[N][N];
bool vis[N][N];

void dfs_floodfill(int x, int y) {
    vis[x][y] = true;  // Mark as visited
    
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (g[a][b] == '#') continue;
        if (vis[a][b]) continue;
        
        dfs_floodfill(a, b);
    }
}

Memoized Search (DFS + Dynamic Programming)

This powerful technique combines DFS with caching to avoid redundant computations:

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int n, m;
int g[N][N], f[N][N];  // f[i][j] = maximum value starting from (i,j)

int dfs(int x, int y) {
    if (f[x][y] != -1)
        return f[x][y];  // Return cached result
    
    f[x][y] = 1;  // At least includes itself
    
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        
        if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] < g[x][y]) {
            f[x][y] = max(f[x][y], dfs(a, b) + 1);
        }
    }
    
    return f[x][y];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
    
    memset(f, -1, sizeof f);  // Initialize with -1 (uncomputed)
    
    int res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            res = max(res, dfs(i, j));
    
    cout << res << endl;
    return 0;
}

Practical Problem Examples

Example 1: Enumerate Tuples (Luogu B3621)

Problem: Generate all possible tuples of length n with values from 1 to k.

Solution:

void dfs(int pos) {
    if (pos == n + 1) {
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
        return;
    }
    
    for (int i = 1; i <= k; i++) {
        a[pos] = i;
        dfs(pos + 1);
    }
}

Example 2: Enumerate Subsets (Luogu B3622)

Problem: Generate all subsets, represented as Y/N for each element.

Solution:

string s;
int n;

void dfs(int pos, int choice) {
    if (choice == 0) s += 'N';
    if (choice == 1) s += 'Y';
    
    if (pos == n) {
        cout << s << endl;
        s = s.substr(0, s.size() - 1);  // Backtrack
        return;
    }
    
    dfs(pos + 1, 0);
    dfs(pos + 1, 1);
    s = s.substr(0, s.size() - 1);  // Backtrack
}

Example 3: Sudoku Solver (4×4)

Problem: Complete a 4×4 Sudoku grid.

Solution:

vector<vector<int>> g(4, vector<int>(4, 0));

bool check(int r, int c, int num) {
    // Check row
    for (int j = 0; j < 4; j++)
        if (g[r][j] == num) return false;
    
    // Check column
    for (int i = 0; i < 4; i++)
        if (g[i][c] == num) return false;
    
    // Check 2×2 box
    int br = (r / 2) * 2;
    int bc = (c / 2) * 2;
    for (int i = br; i < br + 2; i++)
        for (int j = bc; j < bc + 2; j++)
            if (g[i][j] == num) return false;
    
    return true;
}

bool solve() {
    int r, c;
    if (!nextfind(r, c)) return true;  // No empty cells
    
    for (int num = 1; num <= 4; num++) {
        if (check(r, c, num)) {
            g[r][c] = num;
            if (solve()) return true;
            g[r][c] = 0;  // Backtrack
        }
    }
    return false;
}

Key Takeaways

1. Understand the Pattern: Most DFS problems follow the "select or not select" or "try all possibilities" pattern.
2. Master Backtracking: Always restore state after recursive calls when using global variables.
3. Pruning is Crucial: Add early termination conditions to avoid exploring invalid paths.
4. Practice Variations: Work through different problem types (permutations, combinations, subsets, paths) to build intuition.
5. Know When to Use Memoization: If the same subproblems are solved repeatedly, consider caching results.
6. Memory Management: Be aware of array size limits, especially for multi-dimensional arrays in competitive programming.

This guide provides a solid foundation for tackling DFS-based problems. Regular practice with these templates will significantly improve your problem-solving speed and accuracy in competitive programming scenarios.

This comprehensive guide consolidates essential DFS patterns and techniques. Save it as a reference for your competitive programming journey.