有 A B C D E F G H I J K ... 等N个数

xiangsiyu21945

有 A B C D E F G H I J K ... 等N个数字（字母取值范围是 1 到 9）,列出在其中加如一个=号，任意多个加号组成一个等式的所有组合
       
像 AB + C + DEF = GH + I +J + K
或者A + B + CDE + FG = H + IJK

额，⊙﹏⊙b汗，求大家指点迷津，俺不会说话，谢谢啊！
************************************************************
就是从键盘输入N个数，每次输入的数是1到9之间的数，然后在 输入的N 个数之间 加一个 =  号，【若干】 + 号，组成一个【等式】，列出能组成 等式的组合
************************************************************

楼下说 = 号的位置 在1 到N/2 之间，说明 理解错题意了：
比如输入： 1  1  1  2  2  3  6  7                 1+1+1+2+2+3 = 6+7

hgrany

用C语言编写 或 给出思路

这口气....你是来给大家面试的吗?

xiangsiyu21945

额，我错了，我是来求大家指点的，指点一下思路

frank529

n个数，有n-1个间隔，放1个=号，0 ~ (n-2)个+号，穷举构造符号数组，分析等式是否成立

koolcoy

回复 4# frank529

这个问题明显穷举不行，指数级的复杂度。{:3_195:}
看看有没有啥好的dp算法
   

enough_zerg

从中间开始搞起

先把等号放最中间,发现左边大就把等号往左边移,反之则往右边动

直到移动到两个边界

x5miao

什么叫A B C D等N个数字？字母的取值范围怎么是1至9

xiangsiyu21945

关键还包括了  AB + CD = E + F 这种类型，  1 ，2,3,4,4,6，  （  12 + 34 = 46）   ，现在 头都大了

xishuaiya

提供一个很粗糙的思路哈，也是最笨的方法：
“=”所在的位置为1~N/2
for（“=”号位置）{
    当等号位置在n时，“=”前面有n个数字；
    使用n个数字、任意个+号，组合出等式
}

这样，问题就变为：怎么把n个数字用k个“+”号连接起来

koolcoy

这个问题有个重要的剪枝办法：等号左右两边除以3的余数必须相等。也就是等号两边的数字加起来除以3的余数必须相等。

剪枝是次要的，主要还是那个dp