1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; 

using LL = long long int;

void mod(LL& count)
{
    count = count % 1000000007;
}
void print(vector<LL> const& vec)
{
    for(auto const& x : vec)
    {
        std::cout << x << " ";
    }
    std::cout <<std::endl;
}
void subsetsUtil(vector<int> const& A, vector<int>& subset, int index, LL suma, LL& count) 
{ 
	for (int i = index; i < A.size(); i++) { 
        if (A.at(i) > (suma+1))
        {
            return;
        }
        ++count;
        mod(count);
		subset.push_back(A.at(i)); 
        suma += A.at(i);
		subsetsUtil(A, subset, i + 1, suma, count); 
		subset.pop_back(); 
        suma -= A.at(i);
	} 
	return; 
} 

vector<vector<int> > subsets(vector<int> const& A) 
{ 
	vector<int> subset; 
	vector<vector<int> > res; 
	int index = 0; 
    LL count = 0;
	subsetsUtil(A, subset, index,0, count); 
    std::cout << count << std::endl;
	return res; 
} 

void solve(vector<int> const& array)
{
    int count = 0;
    for (auto const& x : array)
        count += x;
    std::vector<LL> dp(count, 0);
    int lastMax = 1;
    dp[0] = 1;
    for (int j = 1; j<array.size(); ++j)
    {
        int x = array.at(j);
        if (lastMax + 1 < x)
            break;
        for (int i = lastMax - 1; i>=x-2; --i)
        {
            dp[i+x] += dp[i];
        }
        lastMax += x;
    }
    LL suma = 0;
    for (int i = 0; i < lastMax && i <dp.size(); ++i)
    {
        suma += dp[i];
        mod(suma);
    }

    std::cout << suma << std::endl;
}

int main() 
{ 
	vector<int> array;
    int n;
    std::cin >> n;
    for (int i = 0; i<n; ++i)
    {
        int a;
        std::cin >> a;
        array.push_back(a);
    }
    std::sort(array.begin(), array.end());
    subsets(array); 
    // solve(array);
	return 0; 
}