【C++】已通过，利用动态规划

using namespace std;
int a[21];
int mem[21][41];
//求拿礼物方法总数，m种商品，容积capacity
int ways(int m, int capacity) {
	if (capacity < 0) {
		return 0;
	}
	if (capacity == 0) {
		mem[m][capacity] = 1;
		return 1;
	}
	if (m == 0 && capacity != 0) {
		mem[m][capacity] = 0;
		return 0;
	}
	if (mem[m][capacity] != -1) {
		return mem[m][capacity];
	}
	else {
		//核心递推
		mem[m][capacity] = ways(m - 1, capacity) + ways(m - 1, capacity - a[m]);
		return mem[m][capacity];
	}
}
int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j < 41; j++) {
			mem[i][j] = -1;//刷新DP记忆数组
		}
	}
	cout << ways(n, 40) << endl;
	return 0;
}