Just posting this to link as a solution to: https://blog.svpino.com/2015/05/08/solution-to-problem-5-and-some-other-thoughts-about-this-type-of-questions

Permutations are a fun alternative to recursion. The three possibilities +, -, and (concatenation) in the 8 places between the numbers can easily be represented as an 8-digit number in base 3. Representing that number as an array and incrementing it one by one allows you to iterate through all possibilities without recursion, taking each individual digit in the array as binary function between i+1 and i+2. No allocations!

#include <stdio.h>

void inc_field(int field[8]){

	field[7]++;

	for (int i = 7; i >= 0; i--){
		switch (field[i]){
			case 4:
			case 3:
				field[i] = (field[i])%3;
				if (i-1 >= 0) field[i-1]++;
				break;

			default:
				break;
		}
	}
}

int field_get_item(int field[8], int i){

	int left = i+1;

	if (i > 7)
		return left;

	switch(field[i]){
		case 0:
			while (i < 8 && field[i] == 0){
				left = left*10 + (i+2);
				i++;
			}
			break;
		default:
			break;
	}

	return left;
}

int field_next_pos(int field[8], int i){

	if (field[i] != 0) 
		return i;

	while (i < 8 && field[i] == 0)
		i++;

	return i;
}

void print_field(int field[8]){

	for (int i = 0; i < 8; i++){
		putchar(i + '0' + 1);
		if (field[i] == 1)
			putchar('+');
		if (field[i] == 2)
			putchar('-');
	}

	putchar('9');
}

int main(int argc, char **argv){

	// 0 = nothing, 1 = +, 2 = -
	int field[8] = {0};

	// 3 values per position, 1,2,3,4,5,6,7,8,9 == 8 positions, 3^8 == 6501
	for (int i = 0; i < 6561; i++){

		int hold = 0;
		int j = 0;

		hold = field_get_item(field, j);

		while (j < 8){

			int n = field_next_pos(field, j);
			int right = field_get_item(field, n+1);

			switch(field[n]){
				case 1:
					hold += right;
					break;
				case 2:
					hold -= right;
					break;
			}

			j = field_next_pos(field, n);
			if (j == n) j++;
		}

		if (hold == 100){
			print_field(field);
			printf(" == %d\n", hold);
		}

		inc_field(field);
	}

	return 0;
}

Result:

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