1370. 零和序列

枚举每次选择的三种运算符：\(\{‘\ \ ‘,‘+‘,‘-‘\}\)(字典序)，时间复杂度为\(O(3^{n-1}),n \le 9\)。

注意点

在数字\(1\)前加一个\(‘+‘\)方便表达式求值。

char path[10];
char op[]={‘ ‘,‘+‘,‘-‘};
int n;

bool check()
{
    int res=0;
    for(int i=1;i<=n;i++)  // 枚举当前运算数
    {
        if(path[i] == ‘+‘ or path[i] == ‘-‘)
        {
            int j=i+1;
            int t=i;
            while(j <= n && path[j] == ‘ ‘)  //双指针求出超过一位的运算数
            {
                t = t*10 + j;
                j++;
            }
            
            if(path[i] == ‘+‘) res += t;
            else res -= t;
            
            i=j-1;
        }
    }
    return res == 0;
}

void dfs(int u)
{
    if(u > n)
    {
        if(check())
        {
            for(int i=1;i<=n;i++)
            {
                if(i > 1) cout<<path[i];
                cout<<i;
            }
            cout<<endl;
        }
        return;
    }

    for(int i=0;i<3;i++)
    {
        path[u]=op[i];
        dfs(u+1);
    }
}

int main()
{
    cin>>n;

    path[1]=‘+‘;
    dfs(2);
    //system("pause");
    return 0;
}

1370. 零和序列

原文：https://www.cnblogs.com/fxh0707/p/14852814.html