如何添加运算符

//动态方程（有点难理解）：当前种类=符号位加号+符号为减号+没有符号的种类
//dp(before,des,n,ex)= dp(before - 1, before, res + des,1) + dp(before - 1, before, res - des,1) + dp(before - 1, before*pow(10, ex)+des, res,ex+1);
// before: 需要判定的符号前面的数字的个数，初始为8
// des: 需要判定的符号后面的数字，初始为9
// n:方程右边的结果
// ex:阶乘数，因为符号有三种可能，加号，减号，或者没有，如果没有，那么ex就用于计算当前值
#include<iostream>
#include<cmath>
using namespace std;
int dp(int before, int des, int res, int ex) {
	if (before == 0) {
		if (des == res) {
			return 1;
		}
		else {
			return 0;
		}
	}
	else {
		return dp(before - 1, before, res + des, 1) + dp(before - 1, before, res - des, 1) + dp(before - 1, before*pow(10, ex) + des, res, ex + 1);
	}
}
int main() {
	int m,n; 
    cin >>m>>n;
    
	cout << dp(m-1, m, n, 1);

}

dfs解法

#include <iostream>
using namespace std;
int n, m;
int dfs(int sum, int current,int step) {
    //当前和，当前位，当前数字（步数）
    if (step == n + 1) {
        if (sum == m&&current == step) {
            return 1;
        }
        else return 0;
    }
        //当当前位为一的时候，不允许减操作，如1 2 3 得到-15，通过-12-3是不允许的。同理1也不能得到-1
    int temp = current;
    while (temp > 9 ) {
        temp = temp / 10;
    }
    if(temp ==1) return dfs(sum + current, step + 1, step + 1) + dfs(sum, current * 10 + step + 1, step + 1);
    else return  dfs(sum + current, step + 1,step+1) + dfs(sum - current, step + 1,step+1) + dfs(sum, current *10+ step +1,step+1);
}
int main() {
    cin >> n >> m;
    cout << dfs(0, 1,1);
    system("pause");
    return 0;
}

""""
DFS，用了eval直接字符串转表达式
"""
def dfs(s, n, m, step):
    s += str(step)
    if step == n:
        if eval(s) == m:
            return 1
        return 0
    return dfs(s + '+', n, m, step + 1) + dfs(s + '-', n, m, step + 1) + dfs(s, n, m, step + 1)


if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    ans = dfs("", n, m, 1)
    print(ans)

	

#include <stdio.h>
int n,m,count=0;
void getcount(int sum,int num,int step){  //分别为 当前和  当前数字  当前步数
    if(step == n+1){
        if(sum == m && num == step)  //当num!=step时说明上一次有num*10....的存在，sum值没有改变
            count ++;
        return;
    }
    int temp = num;   //判断num首位是否为1
    while(temp > 9)
        temp = temp/10;
    //为1则不能进行减运算，1无法变为-1
        //两种情况下按照题目意思进行穷举
    if(temp == 1){
        getcount(sum+num, step+1, step+1);
        getcount(sum, num*10+step+1, step+1);
    }
    else{
        getcount(sum+num, step+1, step+1);
        getcount(sum-num, step+1, step+1);
        getcount(sum, num*10+step+1, step+1);
    }
}
int main(){
    scanf("%d %d", &n,&m);
    getcount(0,1,1);   //初始条件下sum为0,当前步数已经数字均为1
    printf("%d", count);
    return 0;
}

import java.util.Scanner;

public class Main {
    
    private static int num;
    private static int target;
    private static int count=0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        num = scanner.nextInt();
        target = scanner.nextInt();
        dfs(0, 1);
        System.out.println(count);
    }

    private static void dfs(int sum,int p){
        if (sum==target&&p==num+1)
            count++;
        int t=0;
        for (int i = p; i <=num; i++,t*=10) {
            t+=i;
            dfs(sum+t,i+1);
            if (p!=1){
                dfs(sum-t,i+1);
            }
        }
    }
}

#include<iostream>
#include<cmath>
using namespace std;
/*   由后向前确定符号
*    0+1 ----(b-1)？ b ？ a = m 
*   情况1. 0+1 ----(b-1) ？b + a = m     0+1 ----(b-1)？ b = m-a
    情况2. 0+1 ----(b-1) ？b - a = m     0+1 ----(b-1)？ b = m+a
    情况3. 0+1 ----(b-1) ？ba = m        0+1 ----(b-1)？ ba = m
*/
int Solution(int b, int a, int digit, int m) {
    // b 是待定符号前的数字 个位数
    // a 是待定符号后的数字
    // digit  a的位数，用来确定ba的数值 ba=b * pow(10, digit) + a
    // m 为等式的右值
	
	if (0 == b)    // // 递归基,1前隐含0+1，首个符号确定为加号
	{
		if (a == m) return 1;
		else return 0;
	}
	else    // 递归
	{
		return Solution(b - 1, b, 1, m - a)    // b 与 a 之间是加号，对应情况1
			+ Solution(b - 1, b, 1, m + a)     // b 与 a 之间是减号，对应情况2
			+ Solution(b - 1, b * pow(10, digit) + a, digit + 1, m); // b 与 a 之间无符号，对应情况3
	}
}

int main() {
	int n, m, cnt = 0;
	cin >> n >> m;
	cnt = Solution(n - 1, n, 1, m);
	cout << cnt << endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

int n,m,cnt=0;

void DFS(int sum, int p){
    if(sum==m && p==n+1)
        cnt++;
    int t = 0;
    for(int i=p;i<=n;i++,t*=10){
        t += i;
        DFS(sum+t, i+1);
        if(p!=1)
            DFS(sum-t,i+1);
    }
}

int main(){
    cin>>n>>m;
    DFS(0,1);
    cout<<cnt<<endl;
    return 0;
}

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
}

#include <iostream>
#include <vector>
using namespace std;

// 创建新的数组， used[i]表示当前数字前面是否是 “ ”
void MakeNewVector(vector<int> & used, vector<int>& cur_nums, vector<int> & new_nums) {
  new_nums.push_back(cur_nums[0]);
  for (int i = 1; i < used.size(); ++i) {
    // 如果当前第i-1后面是空格
    if (used[i]) {
      // 将最后一个和当前cur_numns[i]合成一个
      new_nums[new_nums.size() - 1] = new_nums[new_nums.size() - 1] * 10 + cur_nums[i];
    }
    else {
      new_nums.push_back(cur_nums[i]);
    }
  }
}

int sum_nums(vector<int>& nums, int S) {
  int sum = 0;
  for (int num : nums) {
    sum += num;
  }

  if ((S + sum) % 2 == 1 || sum < abs(S)) {
    return 0;
  }

  int bagSize = (S + sum) / 2;
  vector<int> dp(bagSize + 1, 0);
  dp[0] = 1;
  for (int i = 0; i < nums.size(); i++) {
    for (int j = bagSize; j >= nums[i]; j--) {
      dp[j] += dp[j - nums[i]];
    }
  }
  return dp[bagSize];
}

void BackStrack(vector<int>& cur_nums, vector<int>& used, int pos, int N, int target, int& sum) {
  // 如果已经遍历完
  if (pos == N) {
    vector<int> new_nums;
    MakeNewVector(used, cur_nums, new_nums);
    // 对cur_nums，找合法种数
    int temp = new_nums[0];
    // 如果pos不为1，将cur_nums[1] 去掉
    new_nums.erase(new_nums.begin());
    // 更新当前的合法序列个数
    sum += sum_nums(new_nums, target - temp);
    return;
  }

  // 对于该位置有合并和不合并两种选择
  for (int i = 0; i <= 1; ++i) {
    // 对 pos 这个位置进行 “ ”
    if (i) {
      // + " "
      // 将对应的used[i] --> 1 添加 “ ”
      used[pos] = 1;
      BackStrack(cur_nums, used, pos + 1, N, target, sum);
      // = " "
      used[pos] = 0;
    }
    else {
      // 直接传递当前的数组
      BackStrack(cur_nums, used, pos + 1, N, target, sum);
    }
  }
}


// 回溯 + 01背包动态规划
int main() {
  int N, target, sum = 0;
  // 输入 N 的大小
  cin >> N >> target;
  vector<int> nums(N, 1);
  // N个数 N-1个空位，所以pos从1开始
  vector<int> used(N, 0);
  // 变成递增数组
  for (int i = 1; i < nums.size(); ++i) {
    nums[i] = nums[i - 1] + 1;
  }

  // 针对于 + - “ ”，来说，如果直接回溯，四种状态，时间复杂度是3^(N-1), 对 + - 变成背包问题，然后 “ ”采用回溯的方式来组合
  BackStrack(nums, used, 1, N, target, sum);
  cout << sum << endl;
}
// 64 位输出请用 printf("%lld")

#include<bits/stdc++.h>
using namespace std;
int N,M;
void  dfs(int st,int cur,int & res)
{
    if(st==N+1 && cur==M)
    {
        res++;
        return;
    }
    int num=0;
    for(int i=st;i<=N;i++)
    {
        num+=i;
        dfs(i+1,cur+num,res);  
        if(st>1)
            dfs(i+1,cur-num,res);
        num*=10;
    }
}
int main()
{
    while(cin>>N>>M)
    {
        int res=0;
        dfs(1,0,res);
        cout<<res<<endl;
    }
    return 0;
}

def cal(s, a, m, i):
    s += str(a[i])
    if i == len(a)-1:
        resu = eval(s)
        return 1 if resu == m else 0
    return cal(s+'+', a, m, i+1) + cal(s+'-', a, m, i+1) + cal(s+'', a, m, i+1)
n,m = map(int, input().split())
a = list(range(1, n+1))
print(cal('', a, m, 0))

#include<bits/stdc++.h>
using namespace std;
int n, m,c=0;

void dfs(int sum, int step)
{
	int i = 0, t = 0;
	if (sum == m && step == n + 1)c++;
	for (int i = step; i <= n; i++)
	{
		t += i;
		dfs(sum + t, i + 1);
		if (step > 1)dfs(sum - t, i + 1);
		t *= 10;
	}
}
int main()
{
	
	cin >> n >> m;
	dfs(0, 1);
	cout << c << endl;
	return 0;
}

//刚学的回溯法 试试水。没一楼大神那么牛逼。
#include<stdio.h>
(737)#include<stdlib.h>
int n,m;//定义全局变量 n m; 
void fun(char op[],int sum,int prevadd,int a[],int i,int &count)//引用型参数count 用于统计符合条件个数 并回传 
{
	if(i==n)
	{
		if(sum==m)	
		{
/*
			printf("%d",a[0]);
			for(int j=1;j<n;j++)
			{
				if(op[j]!=' ')
				printf("%c",op[j]);
				printf("%d",a[j]);
			}
			printf("==%d\n",m);
*/
			count++;
		}
		return;
	} 
	op[i]='+';
	sum+=a[i];
	fun(op,sum,a[i],a,i+1,count);
	sum-=a[i];
	
	op[i]='-';
	sum-=a[i];
	fun(op,sum,-a[i],a,i+1,count);
	sum+=a[i];
	
	op[i]=' ';
	sum-=prevadd;
	int tmp;
	if(prevadd>0)
		tmp=prevadd*10+a[i];
	else
		tmp=prevadd*10-a[i];
	sum+=tmp;
	fun(op,sum,tmp,a,i+1,count);
	sum-=tmp;
	sum+=prevadd;
}





int main()
{
	int *a;
	char *op;
	int count=0;
	scanf("%d%d",&n,&m);
	a=(int*)malloc(sizeof(int)*n);
	op=(char*)malloc(sizeof(char)*n);
	for(int i=0;i<n;i++)
	a[i]=i+1;
	fun(op,a[0],a[0],a,1,count);
	printf("%d",count);	
	
} 

var line=readline().split(' ').map(Number)
var n=line[0]
var sum=line[1]
var arr=new Array(n+1).join('0').split('');
arr.map((item,i)=>{
    arr[i]=i+1
});
// 两层遍历
var num=0;
var label=['+','-',''];
function dfs(arr){
    var myarr=[];
    if(arr.length==1){
        return arr
    }
    if(arr.length==2){
        for(var j=0;j<3;j++){
            myarr.push(arr[0]+label[j]+arr[1])
        }
        return myarr;
    }
    // 否则
    for(var j=0;j<3;j++){
        var tem=dfs(arr.slice(1));
        for(var k=0;k<tem.length;k++){
            myarr.push(arr[0]+label[j]+tem[k])
        }
    }
    return myarr;
}
var myarr=dfs(arr)
// console.log(myarr)
for(var item in myarr){
    if(eval(myarr[item])==sum){
        num++;
    }
}
console.log(num)

import sys
N, M = sys.stdin.readline().strip().split()
N = int(N)
M = int(M)
nums = [i for i in range(N+1)]
ans = 0
def dfs(N, M, cur, sign, res, i):
    global ans
    if i > N:
        res += cur*sign
        if res == M:
            ans += 1
        return
    dfs(N, M, nums[i], 1, res+cur*sign, i+1)
    dfs(N, M, nums[i], -1, res+cur*sign, i+1)
    dfs(N, M, cur*10+nums[i], sign, res, i+1)

dfs(N, M, 1, 1, 0, 2)
print(ans)

def methods(s, n, m, step):
    s += str(step)
    if step == n :
        if eval(s) == m:
            return 1
        else:
            return 0
    return methods(s+"+", n, m, step+1) + methods(s+"-", n, m, step+1) + methods(s, n, m, step+1)

n, m = map(int, input().split())
print(methods("", n, m, 1))

#include<stdio.h>
#include<string>
#include<iostream>
#include<set>
#include<vector>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
 
int res_count = 0;
int m;
int n;
 
void check_eq(int cur_eq, int step)
{
    if (step > n)
        return;
    if (step == n)
    {
        if (cur_eq == m)
        {
            res_count++;
            return;
        }
         
    }
	if(step <= n-2){
		check_eq(cur_eq + ((step + 1) * 10 + (step + 2)), step + 2);
		check_eq(cur_eq - ((step + 1) * 10 + (step + 2)), step + 2);
	}
    check_eq(cur_eq + (step + 1), step + 1);
    check_eq(cur_eq - (step + 1), step + 1);
    //check_eq(cur_eq * 10 + (step + 1), step + 1);
}
 
 
int main()
{
     
    cin >> n >> m;
    check_eq(1, 1);
	char s[500];
	if( n >1 )
		check_eq(12, 2);
    printf("%d", res_count);
    return 0;
}