This is Third Question from Kickstart Round G — https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e02/000000000018fd5e

Normal 3^n recursion with two cases handled — when no further cases need to be considered, and when all cases are right, passes in the time limit.

I'm not sure if it is just weak test cases or we can prove complexity of the solution.

int n,h;
vector<pair<int,int>> a(21),suffixSum(21);
int ans = 0;

int power3[21];

void dfs(int s1, int s2, int index) {
	if(index==n) {
		if(s1>=h&&s2>=h) ans++;
		return;
	}
    
        // No combination will be right
	if(s1+suffixSum[index].f<h||s2+suffixSum[index].s<h) return;

        // Any combination after this are right
	if(s1>=h && s2>=h) {
		ans += power3[n - index];
		return;
	}

	dfs(s1+a[index].f,s2, index+1);
	dfs(s1,s2+a[index].s, index+1);
	dfs(s1+a[index].f,s2+a[index].s, index+1);
}

signed main() {
	int t = 100;
	cin>>t;

	power3[0] = 1;
	for(int i=1;i<21;i++) power3[i] = power3[i-1]*3;

	for(int a0=1;a0<=t;a0++) {
		cin>>n>>h;

		for(int i=0;i<n;i++) cin>>a[i].f;
		for(int i=0;i<n;i++) cin>>a[i].s;

                sort(a.begin(), a.end(), greater<pair<int,int>>());

		ans = 0;

		suffixSum[n-1] = a[n-1];
		for(int i=n-2;i>=0;i--) {
			suffixSum[i] = {
                                          suffixSum[i+1].f + a[i].f,
					  suffixSum[i+1].s + a[i].s
                                       };
		}

		dfs(0,0,0);

		cout<<"Case #"<<a0<<": "<<ans<<endl;
	}
}