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);