2) There's a good D&C solution for finding the smallest K sums: solve it for two halves of the array and you just need to find the K smallest sums of pairs. Then, you can binsearch the largest sum or use a priority queue to find them in ; that makes the total complexity . (I'm assuming different subsequences with equal powers aren't counted as one value, since there can be less than 2^n possible values otherwise and it would take .)

// Dynamic Programming based solution for Problem 2.
#include<bits/stdc++.h> 
#define ll long long int
#define ld long double
#define pb push_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false)
#define MAX 400000
using namespace std;
int ar[1009];
int dpl[1000000]; // for dp[i-1][]
int dph[1000000]; // for dp[i][]
int h[1000000];
int main()
{
	//ios;
	// dp[i][sum] denotes the number of subsequences ending at index i and having sum = sum.
	// recurrence relation for dp:  dp[i][sum]=dp[i-1][sum-ar[i]]+dp[i-1][sum+ar[i-1]-ar[i]]
	// Space optimization: clearly, dp[i][] depends only on dp[i-1][], and hence, we don't need to make entire 2D dp[i][sum], just 2 dp arrays: dpl[] and dph[]
	// Note that always, sum<MAX. The proof is simple. Sum is maximum when n=log2(10000) (got by solving for n: 2^n=10000). Thus, for n==log2(10000), if all ar[i]==20000, then sum<= n*20000, taking n=20 (> log2(10000)), sum<400000. If n==1000, then sum<= 2*max(ar),
	// because nC2>10000.
	// h[j] stores min(number of subsequences having sum=j,10000).
	int n,q;
	scanf("%d",&n);
	int i,j;
	for(i=0;i<n;i++) scanf("%d",&ar[i]);
	dpl[ar[0]]=1; // base case
	h[ar[0]]++;
	for(i=1;i<n;i++)
	{
		for(j=0;j<=MAX;j++)
		{
			if(j-ar[i]>=0)dph[j]=min(10001,dpl[j-ar[i]]+dpl[j+ar[i-1]-ar[i]]);
			else dph[j]=0;
		}
		for(j=0;j<=MAX;j++) 
		{
			dpl[j]=dph[j];
			h[j]=min(10001,h[j]+dph[j]);
		}
	}
	vector<int> v; // stores the smallest min(2^n,10000) subsequence sums.
	v.pb(0); // for null subsequence
	int idx=0;
	while(v.size()<10009&&idx<=MAX)
	{
		for(i=0;i<h[idx]&&v.size()<10009;i++) v.pb(idx);
		idx++;
	}
	//for(i=0;i<v.size();i++) printf("%d ",v[i]); printf("\n");
	// Answer Queries.
	scanf("%d",&q);
	while(q--)
	{
		int x;
		scanf("%d",&x);
		printf("%d\n",v[x-1]);
	}
	return 0;
}

A faster solution for (2).

Let K be the maximum value of the queries (in this case K ≤ 10000). Consider a DAG. For each 0 ≤ i < N, we have two multi-edges i -> i+1 of costs 0 and (i+1)^th element of the array. The paths from 0 to N correspond to subsequences and vice versa. Now, we need to calculate all K-best shortest paths of this graph.

This problem can be solved by Eppstein's algorithm (paper). Because the graph is DAG, Eppstein's algorithm can run in O(N + K) time. For practical purpose, we can omit Frederickson's algorithm and get simpler algorithm.