C语言回溯法求解LED排列计数：重复计数异常排查

嘿，我看到你在用回溯法计算满足约束的LED排列数量时遇到了结果偏多的问题，核心原因是你的代码没有限制重复选取同一个LED，咱们来一步步解决这个问题：

问题根源分析 #

你的回溯循环里每次都从i=0遍历到n-1，没有记录哪些LED已经被选进当前排列，导致同一个LED被多次使用，自然会产生大量重复的排列，计数结果也就偏多了。除此之外，代码里还有几个小问题会影响逻辑和效率：

• 函数名拼写错误：比如este_valid应该是is_valid，nivel应该是level，is_solultion多了一个字母l
• is_valid函数做了冗余检查：它遍历了所有之前的相邻对，但其实只需要检查**刚加入的LED（当前level位置）和前一个LED（level-1位置）**的约束即可——因为之前的递归步骤已经保证前面的排列是合法的
• is_solution函数的逻辑可以简化，不需要再重复检查整个排列的合法性

修正后的代码 #

#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct {
    char color[20];
    char name[20];
    int intensity;
} led;

// 计算两个LED的强度差绝对值
int get_intensity_diff(led* a, led* b) {
    return a->intensity > b->intensity ? a->intensity - b->intensity : b->intensity - a->intensity;
}

// 验证当前新加入的LED是否满足约束（只需要和前一个比较）
bool is_valid(led* sol, int level, int K) {
    // 只有当至少有两个LED时才需要检查
    if (level < 1) return true;
    
    int prev_idx = level - 1;
    // 检查相邻颜色不同
    if (strcmp(sol[prev_idx].color, sol[level].color) == 0) {
        return false;
    }
    // 检查强度差不超过K
    if (get_intensity_diff(&sol[prev_idx], &sol[level]) > K) {
        return false;
    }
    // 检查不能重复选同一个LED（通过name判断，假设name唯一）
    if (strcmp(sol[prev_idx].name, sol[level].name) == 0) {
        return false;
    }
    return true;
}

// 判断是否是完整解：当level等于n-1时就是完整排列
bool is_solution(int level, int n) {
    return level == n - 1;
}

// 回溯函数，添加used数组标记已使用的LED
int backtracking(led* sol, int n, led* l, int level, int K, bool* used) {
    int sum = 0;
    
    // 如果已经形成完整解，计数+1
    if (is_solution(level, n)) {
        return 1;
    }
    
    for (int i = 0; i < n; i++) {
        // 跳过已经使用过的LED
        if (used[i]) continue;
        
        // 选择当前LED
        sol[level + 1] = l[i];
        used[i] = true;
        
        // 验证当前选择是否合法，如果合法则继续递归
        if (is_valid(sol, level + 1, K)) {
            sum += backtracking(sol, n, l, level + 1, K, used);
        }
        
        // 回溯：取消选择当前LED
        used[i] = false;
    }
    return sum;
}

// 调用示例：初始化所需数组并启动回溯
int count_valid_arrangements(led* leds, int n, int K) {
    led* solution = (led*)malloc(n * sizeof(led));
    bool* used = (bool*)calloc(n, sizeof(bool));
    int result = backtracking(solution, n, leds, -1, K, used);
    
    free(solution);
    free(used);
    return result;
}

关键改动说明 #

1. 添加used布尔数组：用来标记哪些LED已经被选入当前排列，每次递归前检查used[i]，跳过已使用的LED，从根源避免重复选取。
2. 简化is_valid函数：只检查当前新加入的LED和前一个的约束，减少冗余计算，同时保证每一步的合法性。
3. 修正拼写错误：统一函数名和变量名的拼写，避免因笔误导致的逻辑错误。
4. 优化递归终止条件：is_solution只需要判断是否到达最后一个位置，因为前面的每一步都已经通过is_valid验证过合法性。
5. 明确回溯步骤：在递归返回后，将used[i]重置为false，取消当前选择，让该LED可以在其他分支中被使用。

使用注意事项 #

• 假设LED的name字段是唯一的，用来区分不同的LED；如果name不唯一，你需要添加一个唯一标识符（比如id字段）来判断是否重复选取。
• 调用时通过count_valid_arrangements函数初始化所需的数组，避免内存泄漏。

内容的提问来源于stack exchange，提问作者Andreea Negoita