2014华为面试题

描述:    输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号，使得等式成立。

1 2 3 4 5 6 7 8 9 = X

比如：

12-34+5-67+89 = 5

1+23+4-5+6-7-8-9 = 5

样例输入:    5

样例输出:    21

请编写程序，统计满足该输入整数的所有等式的个数。

思路：考虑每个间隔的三种可能，并对剩余元素进行递归调用count函数，

firstNum:表示当前所计算元素的首个元素值(并不一定是NumList[0]); 

numList:表示当前所剩余元素集合，

x:表示当前利用剩余元素集合生成的目标值(可正可负也可能为零); 

n:表示剩余元素个数

int count(int firstNum,int numList[],int x,int n)
{
	//思路，每个空格之间有三种可能，+/-/' '，如何进行处理，

	//printf("%d",numList[0]);
	if (n == 1)
	{
		if (x == firstNum)
			return 1;
		else
			return 0;
	}
	else
	//对num中的元素进行组合，使得其结果 == x,对数组中的首个元素和其之后的内容进行组合
	{
		int count1 = count(numList[1],numList + 1,x - firstNum,n - 1);//+
		int count2 = count(numList[1],numList + 1,firstNum - x,n - 1);//-

		firstNum = firstNum * 10 + numList[1];//将首个元素与第二个元素直接合并，不添加操作符
		int count3 = count(firstNum,numList + 1,x,n - 1);
		return count1 + count2 + count3;
	}
}
           

测试代码：

int result = count(1,numList,5,9);
	printf("%d\n", result);