回溯框架总结

mingjie

发布于 2022-05-12 10:51:22

3950

文章被收录于专栏：Postgresql源码分析Postgresql源码分析

1 思路

解决全排列问题的一个基本思路就是backtracing：

必读：https://www.cnblogs.com/wuyuegb2312/p/3273337.html#add

必读：https://labuladong.gitbook.io/algo/bi-du-wen-zhang/hui-su-suan-fa-xiang-jie-xiu-ding-ban

框架：

bool finished = FALSE; /* 是否获得全部解? */
backtrack(int a[], int k, data input)
{
    int c[MAXCANDIDATES]; /*这次搜索的候选 */
    int ncandidates; /* 候选数目 */
    int i; /* counter */
    if (is_a_solution(a,k,input))
    process_solution(a,k,input);
    else {
        k = k+1;
        construct_candidates(a,k,input,c,&ncandidates);
        for (i=0; i<ncandidates; i++) {
            a[k] = c[i];
            make_move(a,k,input);
            backtrack(a,k,input);
            unmake_move(a,k,input);
            if (finished) return; /* 如果符合终止条件就提前退出 */
        }
    }
}

DFS函数的三个必须参数：选择路径（部分解）、选择了多少次（深度）、其他（避免重复的数组、输入空间、输出空间等）

　对于其中的函数和变量，解释如下：

a[]表示当前获得的部分解；

k表示搜索深度；

input表示用于传递的更多的参数；

is_a_solution(a,k,input)判断当前的部分解向量a[1...k]是否是一个符合条件的解

construct_candidates(a,k,input,c,ncandidates)根据目前状态，构造这一步可能的选择，存入c[]数组，其长度存入ncandidates

process_solution(a,k,input)对于符合条件的解进行处理，通常是输出、计数等

make_move(a,k,input)和unmake_move(a,k,input)前者将采取的选择更新到原始数据结构上，后者把这一行为撤销。

2 例题

贴几道题的代码，分析里面应用框架的思路：

电话号组合与全排列

示例 1：

输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例 2：

输入：digits = "" 输出：[] 示例 3：

输入：digits = "2" 输出：["a","b","c"]

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

#include "stdlib.h"
#include "string.h"
#include "math.h"

static char *g_keys[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
static int g_keys_size[10] = {1, 1, 3, 3, 3, 3, 3, 4, 3, 4};

char **ans;
unsigned ans_idx;
unsigned digits_size;

void dfs(char *digits, int digit_idx, char *path, int path_idx) {
    if (digit_idx == digits_size) {
        ans[ans_idx] = (char *) malloc((digits_size + 1) * sizeof(char));;
        strcpy(ans[ans_idx++], path);
        return;
    }
    char *letters = g_keys[digits[digit_idx] - '0'];
    for (size_t i = 0; i < strlen(letters); i++) {
        path[path_idx++] = letters[i];
        path[path_idx] = 0;
        dfs(digits, digit_idx + 1, path, path_idx);
        path[--path_idx] = 0;
    }
}

char **letterCombinations(char *digits, int *returnSize) {
    digits_size = strlen(digits);
    if (digits_size == 0) {
        *returnSize = 0;
        return NULL;
    }
    *returnSize = 1;
    for (int i = 0; i < digits_size; i++) {
        *returnSize = (*returnSize) * g_keys_size[digits[i] - '0'];
    }

    ans = (char **) malloc((*returnSize) * sizeof(char *));
    ans_idx = 0;

    char *path = (char *) malloc((digits_size + 1) * sizeof(char));

    dfs(digits, 0, path, 0);
    return ans;
}

全排列

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

https://leetcode-cn.com/problems/permutations/

#include "stdlib.h"
#include "memory"

int **res;
int resN;

void dfs(int *selection, int sNum, int *path, int pIdx, bool *isUsed) {
    if (sNum == pIdx) {
        res[resN] = (int *) malloc(sNum * sizeof(int));
        memcpy(res[resN++], path, sNum * sizeof(int));
        return;
    }
    for (int i = 0; i < sNum; i++) {
        if (isUsed[i]) {
            continue;
        }
        path[pIdx] = selection[i];
        isUsed[i] = true;
        dfs(selection, sNum, path, pIdx + 1, isUsed);
        isUsed[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;
    }


    res = (int **) malloc((*returnSize) * sizeof(int *));
    resN = 0;

    bool *isUsed = (bool *) calloc(numsSize, sizeof(bool));
    int *path = (int *) malloc(numsSize * sizeof(int));

    dfs(nums, numsSize, path, 0, isUsed);
    return res;
}

整理两道题的思路：

一、DFS函数构造

1. 首先要有部分解空间，dfs的一个参数

2. 然后需要有选择空间，dfs的path参数。

3. 然后需要有选择位置深度记录，dfs的depth参数

其他的例如解空间、最终路径长度都可以放到全局变量传入，dfs的变量尽量简单容易理解。

二、DFS函数内

1. 首先判断path的depth是否达标，如达标则把路径搬运到解空间

2. 然后遍历当前层级，实用depth取值，并在循环内递归DFS函数，depth+1

3. 递归后记得把depth+1影响到的数组还原，继续本层遍历

补充：括号生成

https://leetcode-cn.com/problems/generate-parentheses/

示例 1：

输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"] 示例 2：

输入：n = 1 输出：["()"]

void dfs(int n, int left, int right, char *path, int depth, char **result, int *result_idx) {
    if (2 * n == depth) {
        result[*result_idx] = (char *) malloc((2 * n + 1) * sizeof(char));
        result[*result_idx][2 * n] = '\0';
        strcpy(result[(*result_idx)++], path);
        return;
    }
    if (left < n) {
        path[depth] = '(';
        dfs(n, left + 1, right, path, depth + 1, result, result_idx);
    }
    if (right < left) {
        path[depth] = ')';
        dfs(n, left, right + 1, path, depth + 1, result, result_idx);
    }
}

char **generateParenthesis(int n, int *returnSize) {
    char **result = (char **) malloc(sizeof(char *) * 4000);
    *returnSize = 0;
    char *path = (char *) calloc(n * 2 + 1, sizeof(char));
    dfs(n, 0, 0, path, 0, result, returnSize);
    return result;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-04-13，如有侵权请联系 cloudcommunity@tencent.com 删除

https

网络安全

node.js

编程算法