题解 | #训练聪明的牛II#

int cmp(int *a,int *b) {
    return *a<*b;
}
void dfs(int *nums,int size,int sum,int len,int *min,int *flag){
    if(sum<0) return;
    if(sum==0){
        (*min) = fmin((*min),len);
        *flag=1;
        return;
    }
    for(int i=0;i<size;i++){
        int target = sum;
        sum-=nums[i];
        dfs(nums,size,sum,len+1,min,flag);
        if((*flag)==1) return;
        sum = target;
    }
}
int minEatTimes(int* weights, int weightsLen, int totalWeight ) {
    int min=100000;
    qsort(weights,weightsLen,4,cmp);
    int flag=0;
    dfs(weights,weightsLen,totalWeight,0,&min,&flag);
    if(min==100000) return -1;
    return min;
}

回溯+贪心