回溯算法

一、什么时候该想到「回溯 / DFS」？

只要题目出现这些关键词之一，优先考虑回溯：

“所有可能 / 全部方案 / 所有组合”
“列举 / 返回所有”
“是否存在一种方式”
“组合 / 排列 / 子集”
“选择 or 不选择”
“一步一步尝试，失败就退回”

本质一句话：

这是一个「多步决策，每一步有多个选择」的问题

二、回溯题的 5 大核心题型

① 组合类（Combination）

典型题目

电话号码的字母组合
组合总和
k 个数的组合
选若干个元素满足条件

特征

顺序不重要
不允许重复 / 有条件限制
“选哪个”比”选的顺序”重要

抽象模型

在一个候选集合中
一步一步做选择
最终得到一个合法组合

思考套路

当前能选什么？
下一步从哪里开始选？
什么时候算完成？

模板（核心）

void dfs(int start) {
    if (满足条件) {
        保存结果;
        return;
    }
    for (int i = start; i < n; i++) {
        选择 i;
        dfs(i + 1);
        撤销选择;
    }
}

注意： 在组合类问题中，通过控制起始索引避免重复选择，确保组合的唯一性。

② 排列类（Permutation）

典型题目

全排列
字符串全排列
有 / 无重复元素的排列

特征

顺序很重要
同样的数字换顺序算不同结果

抽象模型

每一位都要选一个没用过的数

思考套路

当前是第几位？
哪些元素还没用？
用一个 visited[] 标记

模板

void dfs(int depth) {
    if (depth == n) {
        保存结果;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = 1;
        path[depth] = nums[i];
        dfs(depth + 1);
        used[i] = 0;
    }
}

注意： 排列类需要使用 visited 数组来标记已使用的元素，避免重复使用同一元素。

③ 子集类（Subset / 选或不选）

典型题目

子集
子集 II（含重复）
所有子序列

特征

每个元素只有两种状态：选 / 不选
没有顺序概念

抽象模型（决策树）

1
2
3

    []
  /    \
选      不选

思考套路

到第 i 个元素
做 2 个决定

模板

void dfs(int i) {
    if (i == n) {
        保存结果;
        return;
    }
    // 不选
    dfs(i + 1);

    // 选
    path.push(nums[i]);
    dfs(i + 1);
    path.pop();
}

注意： 子集类通过递归遍历每个元素的选择状态，生成所有可能的子集。

④ 路径 / 棋盘 / 搜索类（DFS 搜索）

典型题目

单词搜索
迷宫路径
N 皇后
数独

特征

在「二维 / 多维空间」中走
有方向、边界、障碍
常有 visited 标记

抽象模型

从一个点出发
向多个方向尝试
不合法就退回

思考套路

当前在哪？
能往哪走？
什么时候停止？
如何标记访问？

模板

void dfs(int x, int y) {
    if (越界 / 不合法) return;
    if (找到答案) return;

    visited[x][y] = 1;
    for (方向) {
        dfs(nx, ny);
    }
    visited[x][y] = 0;
}

注意： 在搜索类问题中，visited 数组防止重复访问同一位置，确保路径的正确性。

⑤ 分割 / 构造类（切分字符串）

典型题目

回文串分割
IP 地址还原
表达式添加运算符

特征

从字符串中「切一刀」
每一段要合法

抽象模型

当前位置开始
尝试切不同长度

思考套路

从哪切？
切多长？
这一段是否合法？

模板

void dfs(int start) {
    if (start == len) {
        保存结果;
        return;
    }
    for (int i = start; i < len; i++) {
        if (合法(start, i)) {
            path.push(s[start..i]);
            dfs(i + 1);
            path.pop();
        }
    }
}

注意： 分割类需要验证每段的合法性，如回文或有效IP段。

三、回溯题要素

一步要做什么决定？
选哪个数？
往哪个方向走？
切多长？
选择列表是什么？
当前能选的所有可能
什么时候结束？
深度到头
条件满足
如何回退？
覆盖
pop
visited 还原

回溯算法的核心在于通过递归探索所有可能的解决方案，并在不满足条件时回退。实践中，要注意剪枝优化，避免不必要的计算。

四、回溯算法的剪枝优化

剪枝的基本概念

如何剪枝： 通过在递归过程中添加条件判断，提前终止不可能成功的分支，从而减少搜索空间，提高效率。

什么时候剪枝： 当当前状态或路径不可能达到目标条件时，进行剪枝。例如，当前和超过目标、剩余元素不足等。

常见剪枝技巧分类讨论

1. 排序去重剪枝

适用题型： 组合类（Combination）、子集类（Subset）中含有重复元素的题目，如子集 II、组合总和 II。
如何剪枝： 对候选数组进行排序，在选择元素时跳过与前一个相同的元素，避免生成重复结果。

代码示例：

// 在组合类中
for (int i = start; i < n; i++) {
    if (i > start && nums[i] == nums[i-1]) continue;  // 跳过重复
    // 选择 i
}

什么时候使用： 当题目允许重复选择但结果不能重复时。

2. 限制条件剪枝

适用题型： 组合总和类、背包问题变体。
如何剪枝： 在递归中检查当前累积值（如和、积）是否超过限制，如果超过则提前返回。

代码示例：

1	`if (currentSum > target) return; // 组合总和`

什么时候使用： 当有数值限制（如和不能超过目标）时。

3. 长度限制剪枝

适用题型： 组合类（指定组合长度）、排列类（部分排列）。
如何剪枝： 计算剩余可选元素数量，如果不足以达到所需长度，则停止递归。

代码示例：

1	`if (n - i < k - path.size()) return; // k 个数的组合`

什么时候使用： 当组合或排列有固定长度要求时。

4. 对称性剪枝

适用题型： N 皇后、其他对称性问题。
如何剪枝： 利用问题的对称性，只搜索一半或四分之一的空间，然后通过对称生成另一半。
代码示例： 在 N 皇后中，只考虑皇后放在左半边。
什么时候使用： 当问题具有对称性，且结果可以通过对称变换得到时。

5. 搜索类剪枝（路径 / 棋盘）

适用题型： 单词搜索、迷宫路径、数独。
如何剪枝： 使用 visited 数组避免重复访问同一位置；边界检查；提前判断是否可能到达目标。

代码示例：

1	`if (x < 0 \|\| x >= m \|\| y < 0 \|\| y >= n \|\| visited[x][y]) return;`

什么时候使用： 在二维或多维空间搜索时，防止循环和无效路径。

6. 分割类剪枝

适用题型： 回文串分割、IP 地址还原。
如何剪枝： 在分割时，检查当前段是否合法（如是否为回文、有效IP段），不合法则跳过。

代码示例：

1	`if (!isPalindrome(s, start, i)) continue; // 回文分割`

什么时候使用： 当分割后的每段必须满足特定条件时。

五、LeetCode 回溯算法实战合集

1. 分割 / 构造类

这些问题涉及按某些特定条件对字符串、数字等进行切割或构造特定的结构。

131. 分割回文串

LeetCode 131. 分割回文串

核心方向：按回文条件切割字符串，枚举所有回文切割方案。

回溯技巧：递归切割，每次递归检查子串是否为回文。

//1.回溯算法
char*** result;
char** path;
int pathSize = 0;

// 判断s字符串中的子串是否为回文串
bool isPalindrome(char* s, int startIndex, int endIndex){
    while(startIndex <= endIndex){
        if(s[endIndex--] != s[startIndex++]){
            return false;
        }
    }
    return true;
}

void backtracking(char* s, int* returnSize, int startIndex, int** returnColumnSizes){
    if(startIndex == strlen(s)){
        result[*returnSize] = (char**)malloc(sizeof(char*) * pathSize);
        for(int i = 0; i < pathSize; i++){
            result[*returnSize][i] = path[i]; 
        }
        (*returnColumnSizes)[(*returnSize)++] = pathSize;
        return;
    }

    for(int i = startIndex; i < strlen(s); i++){
        if(isPalindrome(s, startIndex, i)){
            char* temp = (char*)malloc(sizeof(char) * (i - startIndex + 2));
            int index = 0;
            for(int j = startIndex; j <= i; j++){
                temp[index++] = s[j];
            }
            temp[index] = '\0';
            path[pathSize++] = temp;
        }
        else{
            continue;
        }
        backtracking(s, returnSize, i + 1, returnColumnSizes);
        
        pathSize--;
    }
}
char*** partition(char* s, int* returnSize, int** returnColumnSizes) {
    result = (char***)malloc(sizeof(char**) * 100000);
    path = (char**)malloc(sizeof(char*) * 100000);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 100000);
    *returnSize = 0;

    backtracking(s, returnSize, 0, returnColumnSizes);
    return result;
}

22. 括号生成

LeetCode 22. 括号生成

核心方向：生成所有合法的括号组合（左括号数 = 右括号数）。

回溯技巧：递归生成括号，剪枝（如左括号数 ≤ n、右括号数 ≤ 左括号数）。

//1.回溯算法
void dfs(char** res, int* returnSize, char* path, int pos, int left, int right, int n) {

    // 终止条件：构造完成
    if (pos == 2 * n) {
        res[*returnSize] = (char*)malloc(2 * n + 1);
        memcpy(res[*returnSize], path, 2 * n + 1);
        (*returnSize)++;
        return;
    }

    // 尝试放 '('
    if (left < n) {
        path[pos] = '(';
        dfs(res, returnSize, path, pos + 1, left + 1, right, n);
    }

    // 尝试放 ')'
    if (right < left) {
        path[pos] = ')';
        dfs(res, returnSize, path, pos + 1, left, right + 1, n);
    }
}

char** generateParenthesis(int n, int* returnSize) {
    *returnSize = 0;
    char** res = (char**)malloc(sizeof(char*) * 1500);
    char* path = (char*)malloc(2 * n + 1);
    path[2 * n] = '\0';

    dfs(res, returnSize, path, 0, 0, 0, n);
    free(path);
    return res;
}

2. 路径 / 棋盘 / 搜索类

这些问题通常涉及在二维或多维的空间中搜索路径。

79. 单词搜索

LeetCode 79. 单词搜索

核心方向：在二维网格中搜索目标字符串的路径。

回溯技巧：标记访问过的格子，避免重复走，剪枝（越界或字符不匹配时终止）。

//1.回溯算法
void backTracking(char** board,int m,int n,char* word,int size,int row,int col,bool* flag,int** used){
    if(*flag) return;
    if(word[size]=='\0'){
        *flag=true;
        return;
    }
    //这里要注意对row和col的越界判断应该放在最前面，否则无法后面的数组判定无法进行
    if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != word[size] || used[row][col] == 1) {
        return;
    }
    used[row][col]=1;
    backTracking(board,m,n,word,size+1,row+1,col,flag,used);
    backTracking(board,m,n,word,size+1,row-1,col,flag,used);
    backTracking(board,m,n,word,size+1,row,col+1,flag,used);
    backTracking(board,m,n,word,size+1,row,col-1,flag,used);
    used[row][col]=0;

}
bool exist(char** board, int boardSize, int* boardColSize, char* word) {
    int m=boardSize;
    int n=boardColSize[0];
    bool flag=false;
    int** used = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
    used[i] = (int*)malloc(n * sizeof(int));
    memset(used[i], 0, n * sizeof(int));
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == word[0]) {  // 如果当前字符匹配，开始回溯
                backTracking(board, m, n, word, 0, i, j, &flag, used);
                if (flag) return true;  // 找到匹配的单词
            }
        }
    }
    for (int i = 0; i < m; i++) {
        free(used[i]);
    }
    free(used);

    return flag;
}

3. 子集类

这些问题通常是枚举所有可能的子集，包含空集。

78. 子集

LeetCode 78. 子集

核心方向：枚举一个集合的所有子集（包括空集）。

回溯技巧：通过 start 参数控制选择顺序，避免重复子集。

//1.递归法（回溯）
void dfs(int* nums, int numsSize, int start,int* path, int pathSize,int** res, int* returnSize, int* colSizes) {
    // 保存当前子集
    res[*returnSize] = (int*)malloc(sizeof(int) * pathSize);
    memcpy(res[*returnSize], path, sizeof(int) * pathSize);
    colSizes[*returnSize] = pathSize;
    (*returnSize)++;

    for (int i = start; i < numsSize; i++) {
        path[pathSize] = nums[i];
        dfs(nums, numsSize, i + 1, path, pathSize + 1, res, returnSize, colSizes);
    }
}

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    int maxSize = 1 << numsSize;
    int** res = (int**)malloc(sizeof(int*) * maxSize);
    *returnColumnSizes = (int*)malloc(sizeof(int) * maxSize);

    int* path = (int*)malloc(sizeof(int) * numsSize);
    *returnSize = 0;

    dfs(nums, numsSize, 0, path, 0, res, returnSize, *returnColumnSizes);

    free(path);
    return res;
}

4. 排列类

这些问题涉及到元素的排列，通常要求考虑元素顺序。

46. 全排列

LeetCode 46. 全排列

核心方向：枚举所有元素的排列。

回溯技巧：标记已使用的元素，避免重复排列。处理重复元素时需要去重。

//1.回溯算法
/*
void backtrack(当前状态, 其他参数) {
    if (满足结束条件) {
        记录结果;
        return;
    }

    for (每个可能的选择) {
        做出选择;           // 修改状态
        backtrack(新状态, ...); // 递归
        撤销选择;           // 恢复状态（关键！）
    }
}
*/

int count;
void DFS(int *nums, int numsSize, int depth, int *path, bool *used, int **res) {

    if (depth == numsSize) {
        res[count] = (int *)malloc(sizeof(int) * numsSize);
        memcpy(res[count++], path, sizeof(int) * numsSize);
        return;
    }

    for (int i = 0; i < numsSize; i++) {
        if (used[i] == true) {
            continue;
        }
        path[depth] = nums[i];
        used[i] = true;
        DFS(nums, numsSize, depth + 1, path, used, res);

        used[i] = false;
    }
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    (*returnSize) = 1;
    for (int i = 1; i <= numsSize; i++) {
        (*returnSize) *= i;
    }

    *returnColumnSizes = (int *)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < (*returnSize); i++) {
        (*returnColumnSizes)[i] = numsSize;
    }

    int **res = (int **)malloc(sizeof(int *) * (*returnSize));
    int *path = (int *)malloc(sizeof(int) * numsSize);
    bool *used = (bool *)calloc(numsSize, sizeof(bool));

    count = 0;
    DFS(nums, numsSize, 0, path, used, res);
    return res;
}

5. 组合类

这些问题通常涉及多个集合的组合或从一个集合中选择元素，可能会有条件限制（如总和、数量等）。

17. 电话号码的字母组合

LeetCode 17. 电话号码的字母组合

核心方向：多个数字对应字母集合，选一个字母组合。

回溯技巧：每次递归选择一个字母，并递归继续选择下一个字母。

//1.回溯 / DFS
char *map[10] = {
    "", "", "abc", "def", "ghi",
    "jkl", "mno", "pqrs", "tuv", "wxyz"
};

void dfs(char *digits, int idx, char *path, char **res, int *returnSize) {
    if (digits[idx] == '\0') {
        int len = strlen(path);
        res[*returnSize] = malloc(len + 1);
        memcpy(res[*returnSize], path, len + 1);  
        (*returnSize)++;
        return;
    }

    char *letters = map[digits[idx] - '0'];
    for (int i = 0; letters[i]; i++) {
        path[idx] = letters[i];
        path[idx + 1] = '\0';
        dfs(digits, idx + 1, path, res, returnSize);
    }
}

char **letterCombinations(char *digits, int *returnSize) {
    *returnSize = 0;
    if (!digits || !digits[0]) return NULL;

    int len = strlen(digits);
    char **res = malloc(sizeof(char *) * 256);
    char path[len + 1];

    dfs(digits, 0, path, res, returnSize);
    return res;
}

39. 组合总和

LeetCode 39. 组合总和

核心方向：从数组中选元素，使其和为目标值，允许重复选择。

回溯技巧：递归选择，控制选择范围，剪枝（如果和超过目标值，则提前停止递归）。

//1.回溯递归
void dfs(int* candidates, int candidatesSize, int target, int* returnSize, int* path, int* returnColumnSizes, int pathSize, int** res, int start) {
    if (target == 0) {
        // 找到一个满足条件的组合
        res[*returnSize] = (int*)malloc(sizeof(int) * pathSize);
        memcpy(res[*returnSize], path, sizeof(int) * pathSize);
        returnColumnSizes[*returnSize] = pathSize;  // 记录当前组合的大小
        (*returnSize)++;  // 更新组合数量
        return;
    }
    
    if (target < 0) {
        return;  // 剪枝：当 target 小于 0 时，当前路径无效
    }

    for (int i = start; i < candidatesSize; i++) {
        path[pathSize] = candidates[i];  // 选择当前候选数
        // 递归，允许同一个数字多次选择，因此 start 还是从 i 开始
        dfs(candidates, candidatesSize, target - candidates[i], returnSize, path, returnColumnSizes, pathSize + 1, res, i);
    }
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    int** res = (int**)malloc(sizeof(int*) * 150);
    int* path = (int*)malloc(sizeof(int) *50);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 150);

    dfs(candidates, candidatesSize, target, returnSize, path, *returnColumnSizes, 0, res, 0);

    free(path);
    return res;
}

leetcode刷题笔记 > C语言

#算法 #回溯

回溯算法

https://moon1784734830.github.io/2026/01/11/回溯算法/

作者

兰卡黄

发布于

2026年1月11日

许可协议

哈希表之Uthash应用上一篇

二叉树系列之递归下一篇