幸运的袋子

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> arr; //全局变量


int bag(int pos,int sum,int product)
{
    int count =0;
    for(unsigned int i=pos;i<arr.size();++i)
    {
        sum+=arr[i];
        product*=arr[i];
        //是幸运袋子
        if(sum>product)
        {
            count=(count+1)+bag(i+1,sum,product);//当前值和下一位数是不是幸运袋子
        }
        else if(arr[i]==1)
        {
            count=count+bag(i+1,sum,product);//当前值和为1时，说明还可以组成幸运袋子
        }
        else
        {
            break;
        }
        //回溯
        sum=sum-arr[i];
        product=product/arr[i];
        //剪枝操作，
        while(arr[i]==arr[i+1] && i<arr.size())
        {
            i++;
        }
    }
    return count;
}

int main()
{
    int num;
    int a,ret;
    while(cin>>num)
    {

        while(num)
        {
            cin>>a;
            arr.push_back(a);
            num--;
        }
        sort(arr.begin(),arr.end());  //排序
        int ret = bag(0,0,1);  //起始位置从0开始，初始和为0，初始积为1
        cout<<ret<<endl;
    }


    return 0;
}