给出一个数字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 }