回溯表达式,+不小于4个,乘号不小于2个，列出表达式种数

#include <iostream>
using namespace std;
//要求1 2 3 4 5 6 7 8 9之间插入运算符+-*/ 
/*使得'+'个数不小于4个，'*'个数不小于2个
输出结果种数*/
char a[] = " +-*/";
int x[9], c1, c2, count, cnt;
int pruning(int k, int i)
{//9个数字8个空位 
	if (i != 1 && c1 + 8 - k < 4)	return 0;//为+时，已有+的个数和剩余空位8-k的个数相加小于4，+的个数一定小于4，不用继续 
	if (i != 3 && c2 + 8 - k < 2)	return 0;//为*时，已有*的个数和剩余空位8-k个数相加小于2，*个数一定小于2 
	if (i != 1 && i != 3 && c1 + c2 + 8 - k < 6)	return 0;//+1个,*1个,剩余空位 为3个，满足前2个条件,但无法同时满足+和*一共6个的条件，剪枝 
	//+*和剩余空位相加小于6不用继续 
	return 1;
}

void output()
{
	printf("\n%d:", ++count);
	for (int i = 1; i < 9; ++i)
	{
		printf("%d", i);
		printf("%c", a[x[i]]);
	}
	printf("9");
}

int f(int k)
{
	++cnt;//总共遍历多少节点 
	if (k - 1 == 8)
	{
		output();
	}
	else
	{
		for (int i = 0; i <= 4; ++i)
		{
			if (pruning(k, i))
			{
				x[k] = i;
				if (i == 1)	++c1;//c1是+的个数 
				if (i == 3)	++c2;//c2是-的个数 
				f(k + 1);
				if (i == 1)	--c1;
				if (i == 3)	--c2;
			}
		}
	}	
}
int main()
{
	f(1);
	printf("\n%d", cnt);
	return 0;
}