给出一个数字N,对于数字序列 1,2,3 ... N。现在在其中插入“+”, "-", " ",使得表达式的和为M。" "的含义是把相邻的两个数字组成一个数。例如:1 + 2 3 - 4,含义是:1 + 23 - 4 = 20。
给出N和M,求出所有合法的序列的个数。
两个整数N,M ( 1 <= N <= 7, -100 <= M <= 100)
合法序列的个数
7 0
6
样例中的六种合法序列
1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7
package main
import (
"fmt"
"strconv"
)
func main() {
var n,m int
fmt.Scan(&n,&m)
ans:=0
var dfs func(string,int)
dfs=func(s string,idx int){
if idx==n+1{
if cal(s)==m{
ans++
}
return
}
dfs(s+"+"+strconv.Itoa(idx),idx+1)
dfs(s+"-"+strconv.Itoa(idx),idx+1)
dfs(s+strconv.Itoa(idx),idx+1)
}
dfs("1",2)
fmt.Print(ans)
}
func cal(s string)int{
arr1,arr2:=[]int{},[]byte{}
pre:=""
for _,ch:=range []byte(s){
if ch=='+'||ch=='-'{
x,_:=strconv.Atoi(pre)
arr1=append(arr1,x)
arr2=append(arr2,ch)
pre=""
}else{
pre+=string(ch)
}
}
x,_:=strconv.Atoi(pre)
arr1=append(arr1,x)
ans:=arr1[0]
for i:=1;i<len(arr1);i++{
if arr2[i-1]=='+'{
ans+=arr1[i]
}else{
ans-=arr1[i]
}
}
return ans
}