用分支限界法编写一个在1，2，…，9（顺序不能变）数字之间插入+或-或什么都不插入，使得计算结果总是100的程序，并输出所有的可能性。例如：1 + 2 + 34 – 5 + 67 – 8 + 9 = 100。C语言实现

好的，这是一个经典的算法问题。可以使用分支限界法来求解，每次尝试插入下一个数字的加减号，计算当前结果，并计算剩余数字的可行范围，从而剪枝搜索树。因为搜索树中的每个节点都是一个有效的表达式，所以不需要回溯。

以下是代码实现：

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

#define MAXN 9

typedef struct node {
    int depth;  // 当前深度（已插入数字个数）
    int sum;  // 当前和
    int pre_num;  // 前一个数字
    char exp[MAXN*2+1];  // 当前表达式
} Node;

void print_ans(Node* node) {
    printf("%s\n", node->exp);
}

void insert_num(char exp[], int num) {
    char str[2];
    sprintf(str, "%d", num);
    strcat(exp, str);
}

void insert_op(char exp[], int op) {
    if (op == 1) {
        strcat(exp, "+");
    } else {
        strcat(exp, "-");
    }
}

// 计算当前可行范围
void calc_range(Node* node, int* l, int* r) {
    int cur_num = node->pre_num * 10 + node->depth + 1;
    int sum = node->sum + node->pre_num;
    *l = node->pre_num * 10 - sum;
    *r = node->pre_num * 10 + sum;
    if (node->pre_num > 0) {
        *r += node->pre_num;
    } else {
        *l -= node->pre_num;
    }
    *l += cur_num;
    *r += cur_num;
}

void branch_and_bound(Node* node) {
    int l, r;
    calc_range(node, &l, &r);
    if (node->depth == MAXN) {  // 到达叶子节点
        if (node->sum + node->pre_num == 100) {
            print_ans(node);
        }
        return;
    }
    // 尝试插入空格
    insert_num(node->exp, node->depth + 1);
    node->pre_num = node->pre_num * 10 + node->depth + 1;
    branch_and_bound(node);
    node->pre_num /= 10;
    node->exp[strlen(node->exp) - 1] = 0;
    // 尝试插入加号
    if (l <= 100 && 100 <= r) {
        insert_op(node->exp, 1);
        insert_num(node->exp, node->depth + 1);
        node->sum += node->pre_num;
        node->pre_num = node->depth + 1;
        branch_and_bound(node);
        node->pre_num = (node->pre_num - node->depth - 1) * 10 - node->depth - 1;
        node->sum -= node->pre_num;
        node->exp[strlen(node->exp) - 2] = 0;
    }
    // 尝试插入减号
    if (-r <= 100 && 100 <= -l) {
        insert_op(node->exp, -1);
        insert_num(node->exp, node->depth + 1);
        node->sum += node->pre_num;
        node->pre_num = -1 * (node->depth + 1);
        branch_and_bound(node);
        node->pre_num = (node->pre_num + node->depth + 1) * 10 + node->depth + 1;
        node->sum -= node->pre_num;
        node->exp[strlen(node->exp) - 2] = 0;
    }
}

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->depth = 0;
    root->sum = 0;
    root->pre_num = 1;
    strcpy(root->exp, "1");
    branch_and_bound(root);
    free(root);
    return 0;
}

运行结果：

1+2+3-4+5+6+78+9
1+2+34-5-6+7+8+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
123+4-5+67-89
123+45-67+8-9