请问一下这应该怎么优化？我写的只能通过一半的数据

Question

用了一定的剪枝，但是还是不能解决超时的问题，代码已附注释

#include<iostream>
#include<algorithm>
using namespace std;
int n,x;
int cnt=0;

void dfs(int start,int a[],int end,int cur,int sum)
//下面对dfs中的部分参数进行说明：
//start:代表每层循环中加数的开始位置，每一层循环的加数开始位置都应该是上一层循环的下一位（因为不能取同一个数，这类似于握手问题）
//end:最多有几个数相加，取决于主函数中for循环的i
//cur:当前这层递归处于那一层也就是说这是第几个数，如果不到end，那么就继续相加
//sum:记录当前的所加和，sum必须到最后一层递归时，才能去比较大小
{
    if(sum==x && cur==end){//如果递归到了最后一层，并且sum等于x，那么就让方案数加一
        cnt++;
        return;
    }
    else if(cur>end || sum>x) return;
    for(int i=start;i<n;i++) dfs(i+1,a,end,cur+1,sum+a[i]);
}

int main(){
    cin>>n>>x;
    int* b = new int[n];
    int ign = n;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        if(t>x) continue;
        else if(t==x) {
            cnt++;
            continue;
        }
        else {
            b[i] = t;
            ign--;
        }
    }
    int* a = new int[n-ign];
    n-=ign;
    for(int i=0;i<n;i++) a[i] = b[i];
    sort(a,a+n,greater<int>());
    for(int i=1;i<=n;i++) dfs(0,a,i,1,0);//i代表有几个加数，如i=1就是只有一个数
    if(!cnt) cout<<"-1";
    else cout<<cnt;
}

Answer 1

把变量前的“int”改为“long long”再试试；
我估计是您没有看数据范围