数字序列和为0-一串数字 添加符号 使其结果为0

数字序列和为0--一串数字 添加符号 使其结果为0

题目：序列123...N，N介于3和9之间，在其中加入+、-或者空格，使其和为0。如123456  1-2 3-4 5+6 7 等价于1-23-45+67=0。请问，如何获得所有组合？

思路：

#include <iostream>#include <string>using namespace std; /* parameter description * * N，1-N 的数字串 * k，处理到第几个字符了,k范围[1-N] * val，当前表达式的值 * result，结果字符串 * pre，记录前一个操作符，用于遇到空格时考虑 */void dfs(int N, int k, int val, string& result, char pre){    if(k > N)    {        if(val == 0)        {            printf("%s\n", result.c_str());        }        return;    }    /* deal space */    int val_space = val;    if(pre == '-')    {        val = val+(k-1)-((k-1)*10+k); //在上一次的操作上，首次是符号入栈 然后是数字如栈 在这里需要将上一次的数字转换    }else if(pre == '+')    {        val = val-(k-1)+((k-1)*10+k);    }else    {        val = val * 10 + k;    }    result.push_back(' ');    result.push_back(k + '0');    dfs(N, k+1, val, result, ' ');     val = val_space;    result.pop_back();    result.pop_back();     /* deal + */    val += k;    result.push_back('+');    result.push_back('0' + k);    dfs(N, k+1, val, result, '+');     val -= k;    result.pop_back();    result.pop_back();     /* deal - */    val -= k;    result.push_back('-');    result.push_back('0' + k);    dfs(N, k+1, val, result, '-');     val += k;    result.pop_back();    result.pop_back();} void main(){    string res = "1";    for(int i = 3; i <= 9; ++i)    {        dfs(i, 2, 1, res, ' ');    }}