正进行一个网上笔试题，感觉挺难的，请高手指点！研究中，在线等。。。
We have a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual. For example, consider the string "12 ". With zero additions, we can achieve the number 12. If we insert one plus sign into the string, we get "1+2 ", which evaluates to 3. So, in that case, given "12 ", a minimum of 1 addition is required to get the number 3. As another example, consider "303 " and a target sum of 6. The best strategy is not "3+0+3 ", but "3+03 ". You can do this because leading zeros do not change the result.
Write a class SimpleSums that contains the method minMSums, which takes a String numbers and an int sum. The method should calculate and return the minimum number of additions required to create an expression from numbers that evaluates to sum. If this is impossible, return -1.
Definition
Class: SimpleSums
Method: minSums
Parameters: String, int
Returns: int
Method signature: int minSums(String numbers, int sum)
(be sure your method is public)
Constraints
- numbers will contain between 1 and 10 characters, inclusive.
- Each character in numbers will be a digit.
- sum will be between 0 and 100, inclusive.
上面是题目，用程序实现。
[解决办法]
最多10个字符；
假如数据字符串长度为n(1 <=n <=10),最多可以插入n-1个 '+ '号，有2^(n-1)个组合。
枚举所有的组合就可以了；
[解决办法]
int minSums(string numbers, int sum)
{
numbers = numbers.TrimStart( '0 ');
if(numbers.Length == 1)
{
if(int.Parse(numbers) == sum )
return 0;
else
{
return -1;
}
}
int firstVal = int.Parse(numbers.Substring(0,1));
int min = -1;
for( int i = 0; i < numbers.Length-1; i ++)
{
if(numbers[i]== '0 ') continue;
firstVal = int.Parse(numbers.Substring(0,i+1));
if(firstVal < sum)
{
int tmp = minSums(numbers.Substring(i+1,numbers.Length-i-1),sum - firstVal);
if( tmp == - 1) return -1;
int temp = tmp+1;
if( temp < min || min == -1)
{
min = temp;
}
}
else
{
break;
}
}
return min;
}
