给定数字N和M，则从数字1到N得序列中添加+或-，使得序列的和最接近M，打印出所有满足此关系的序列，例如，给定N=4 M=6,则满足条件得序列是1-2+3+4=6；
看到这样得题目，第一反应是动态规划，对于每一个数，其有两种取法，+或-，则依次遍历所有得数，尝试这两种可能，最后得出结果。动态规划需要列出详细的递归表达式，定义出递归表达式得意义，给出边界条件，记录递归过程中得中间结果,知道在什么情况下，递归结束。
首先列出递归表达式,F(i,m)表示数组前i的元素通过添加加减号后与整数M之间最小得差距，例如对于上面给出得例子，F(3,6)=0
> F(i,m) = min{|F(i-1,m-a[i])|,|F(i-1,m+a[i])|} ( 0<= i < n)
除了上面得表达式之外，还需要一个二位数组记录中间结果。
根据前面的动态规划分析，则可以按照递归表达式来写出方程。在记录中间结果的时候，target-array[i]可能小于0了，所以使用了一个offset偏移量，保证前面的能够大于0。因为是记录前i个数通过添加加减号之后与M的差距，故只记录绝对值。
int dfsV4(const int* array, int index, int target,int offset, int **state){
if(index == 0){
return abs(target-1,0) < abs(target+1,0) ? target - 1 : target + 1;
}
if(state[index][target+offset] > INT_MIN)
return state[index][target+offset];
int plus = dfsV4(array,index-1,target+array[index],offset,state);
state[index-1][target + array[index] + offset] = plus;
int minus = dfsV4(array,index-1,target-array[index],offset,state);
state[index-1][target - array[index] + offset] = minus;
state[index][target+offset] = abs(plus,0) < abs(minus,0) ? abs(plus) : abs(minus);
return state[index][target+offset];
}
此题的动态规划过程很简单，按照表达式来实现就行了，然后是进行回溯，打印出所有存在的可能组合，
void backtracing(const int *array, int index, int **state, int offset, int target,stack<bool> symbol){
if(index == 0){
if(abs(target + 1,0) < abs(target - 1,0))
symbol.push(true);
else
symbol.push(false);
int i = 0;
while(!symbol.empty()){
if(!symbol.top()){
if(i == 0){
cout << array[i++];
}else{
cout <<"+"<< array[i++];
}
}else{
cout << "-" << array[i++];
}
symbol.pop();
}
cout << endl;
return;
}
int left = state[index-1][target-array[index] + offset];
int middle = state[index][target+offset];
if(middle == left){
symbol.push(false);
backtracing(array,index-1,state,offset,target-array[index],symbol);
}else{
symbol.push(true);
backtracing(array,index-1,state,offset,target+array[index],symbol);
}
int right = state[index-1][target+array[index] + offset];
if(middle == left && middle == right){
symbol.pop();
symbol.push(true);
backtracing(array,index-1,state,offset,target+array[index],symbol);
}
}
测试此代码，给定N = 4，M = 6,则是在1，2，3，4中查找与6最接近得组合。运行结果如下：
1-2-3+4+5
1+2+3-4+5
1+2+3+4-5
虽说有了正确得结果，但是总感觉，还可以定义其他得递归表达式，使思路看上去更加明了和清晰！欢迎大家指导！
关于这个题目得变形有很多，大概都是在数组构造出和为某个值的子序列。例如
在数组中查找和为M的子序列。
将数组划分为和相差最小的两个子数组