#include <iostream>
#include <memory.h>

using namespace std;

int count;
int st2[40];
int n;

void depth(int sum,int position){
	if(sum>40)
		return;
	if(sum==40){
		count++;
		return;
	}

	for(int i=position;i<n;i++)
		depth(sum+st2[i],i+1);
}

int main(){
	while(cin>>n){
		for(int i=0;i<n;i++)
			cin>>st2[i];
		count=0;
		depth(0,0);
		cout<<count<<endl;
	}
	return 0;
}

def findCountsNum(tempSum,nowIndex):   #通过当前的下标和前面加的数字和进行查找
    if nowIndex >= num:
        return
    if tempSum + digitNums[nowIndex] == 40:
        global count
        count += 1
        findCountsNum(tempSum,nowIndex+1)
    elif tempSum+digitNums[nowIndex] < 40:
        findCountsNum(tempSum+digitNums[nowIndex],nowIndex+1)
        findCountsNum(tempSum,nowIndex+1)


while True:
    try:
        num = int(input())
        digitNums = []
        for i in range(num):
            digitNums.append(int(input()))
        digitNums.sort()
        count = 0
        findCountsNum(0,0)
        print(count)
    except Exception:
        break

//动态规划
//具体思想：对于数字dp[i][j]，i代表编历到第i个有序数，总重量为j的方式数目
//dp[i][j]的值只可能来自两个，一是继承自dp[i-1][j],此时是代表第i个有序数没有用到
//二是由dp[i-1][j-q[i]]，q[i]代表第i个有序数，此时是用到了第i个有序数
//注意实现方式，我设-1为不可达，需要判断以上两种情况，加成需要判断四种情况
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        vector<int> Q;
        for(int i=0;i<n;i++)
        {
            int tmp;
            cin>>tmp;
            if(tmp<=40&&tmp>0)   //读数，筛选出小于等于40的值
                Q.push_back(tmp);
        }
        int m=Q.size();
        sort(Q.begin(),Q.end());  //排序
        int dp[m+1][41];  //动态规划数组
        for(int i=0;i<41;i++)
            dp[0][i]=-1;  // 0个物品只有0可达，其余不可达。
        dp[0][0]=1;
        for(int i=1;i<=m;i++)
        {
            int tmp=Q[i-1];
            for(int j=0;j<41;j++)
            {
                if(j-tmp<0)  //j小于tmp的只能继承自dp[i-1][j];
                {
                    dp[i][j]=dp[i-1][j];
                }
                else
                {
                    if(dp[i-1][j]==-1&&dp[i-1][j-tmp]==-1)  //四种情况，两个数值的存在不存在
                        dp[i][j]=-1;
                    else if(dp[i-1][j]!=-1&&dp[i-1][j-tmp]==-1)
                        dp[i][j]=dp[i-1][j];
                    else if(dp[i-1][j]==-1&&dp[i-1][j-tmp]!=-1)
                        dp[i][j]=dp[i-1][j-tmp];
                    else
                        dp[i][j]=dp[i-1][j]+dp[i-1][j-tmp];
                }
            }
        }
        if(dp[m][40]==-1) cout<<"0"<<endl; //不存在输出0
        else cout<<dp[m][40]<<endl;  //存在输出
    }
}

#include<stdio.h>
#include<string.h>
int main(){
    int target[41], i, j, volume[20], n;
    while(scanf("%d", &n) != EOF){
        for(i=0; i<n ; ++i)
            scanf("%d", &volume[i]);
        memset(target, 0, sizeof(int)*41);
        target[0] = 1;
        for(i=0 ; i<n ; ++i)
            for(j=40; j>=volume[i] ; --j)
                target[j] = target[j] + target[j-volume[i]];
        printf("%d\n", target[40]);
    }
    return 0;
}

法一 ：递归  把物品数目n和物品体积数组a[100]设为全局变量; 
count(i,sum)表示从数组的第i个数开始往后统计的组合数和为sum的种类数，
sum为组合数的和,则：cout(i,sum)=cout(i+1,sum-a[i])+cout(i+1,sum）,
其中cout(i+1,sum-a[i])表示包含了a[i]，即为从第i+1个数开始往后统计
组合数的和为sum-a[i]的种类数, 而cout(i+1,sum）表示不包含a[i]， 即为从第i+1个数开始往后统计组合数的和为sum的种类数 ***********************************
#include<iostream>
using namespace std;
    
int a[100];
int n=1;
int count(int i,int sum)
{
    if(sum==0){return 1;} //找到一组和为sum的组合数；
    if(i==n||sum<0) return 0;//i==n说明没有其他的数来组合，sum<0说明组合不出;
    return count(i+1,sum-a[i])+count(i+1,sum);//从数组的第i为开始，包含a[i],和不包含;
}

int main()
{
    while(cin>>n){
    for(int i=0;i<n;i++)
      cin>>a[i];
    cout<<count(0,40)<<endl;
    }
    return 0;
} 

法二:动态规划
 #include<iostream>
using namespace std;
#define N 100
int n,a[N]; 
int main()
{
    while(cin>>n){
    int (*dp)[50]=new int[N][50];//dp[i][j]表示从前i个物品中凑出体积j；
    for(int i=1;i<=n;i++)
    {
      cin>>a[i];
      dp[i][0]=1; //初始边界
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=40;j++)
      {
        dp[i][j]=dp[i-1][j];
        if(a[i]<=j)
          dp[i][j]+=dp[i-1][j-a[i]];
      }
    cout<<dp[n][40]<<endl;
    delete []dp;
    }
    return 0;
} 
******************************************************************
***************************************************************** 法三：动态规划，对值域空间-即对容积的可达性进行动态 规划。定义一维数组 int dp[N];
依次放入物品，计算每次放入物品可达的容积， 并在相应空间设置记录，最后判断dp[40] 是否可达 ，到达了几次
#include<iostream>
using namespace std;
#define N 100
int n,a; 
int main()
{
    while(cin>>n){
    int *dp=new int[N];//dp[j]表示凑出体积i的次数；
    for(int i=1;i<=n;i++)
    {
      cin>>a;
      for(int j=40;j>=1;j--) //逆序，不然重复更新
       if(dp[j]>0&&j+a<=40)
          dp[j+a]+=dp[j];//如果j有dp[j]种方式可达，则每种方式加上a就可达j+a
      dp[a]++;
    }
    cout<<dp[40]<<endl;
    delete []dp;
    }
    return 0;
}

本题采用递归思想：
①物品n个，物品体积逐一放入a[100]中
②递归函数count(i,sum)=count(i+1,sum-a[i])+count(i+1,sum); 
其中，i为第i个物品，sum代表剩余空缺体积数 
count(i+1,sum-a[i]) 代表从第i+1个物品开始，剩余体积数为sum-a[i]的方案数
（隐含：已经将a[i]的体积计算进去，即包含a[i]的体积）  
count(i+1,sum) 代表从第i+1个物品开始，剩余体积数为sum的方案数 
（隐含：不将a[i]的体积计算进去，即不包含a[i]的体积） 
 
代码如下：
#include<stdio.h>

int a[100];
int n=1;

int count(int i,int sum){   //递归函数
    if(sum==0) return 1;
    if(i==n||sum<0) return 0;
    return count(i+1,sum-a[i])+count(i+1,sum);
}
int main(){
  while(scanf("%d",&n)!=EOF){
     for(int i=0;i<n;i++)   scanf("%d",&a[i]);
     printf("%d",count(0,40));
  }
  return 0;
}

/*dp[i]指口袋体积为i时，共有几种方法
  对于所有物品进行遍历，该物体体积为volume[i]
*/
//用滚动数组法,每次状态转移仅仅根据前一行数组决定，故选择用一维数组
#include<cstdio>
int volume[21];
int dp[41];

int main()                                
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        for (int i = 1; i<=n; i++)        //输入物品的体积
            scanf("%d", &volume[i]);
        for(int i = 1; i<=n; i++)    //对于所有物品进行遍历，该物体体积为volume[i]
        {
            for(int j = 40; j>=volume[i]; j--)    //j>=volume[i]因为dp[j]只能从0~40-volume[i]的状态转移而来
            {
                dp[j] += dp[j-volume[i]]; //如果dp[j]已经有了x种方法，而dp[j-volume[i]]也有y种方法
            }                   //那么由于物体i的存在，对于体积为j的口袋，又能多出dp[j-volume[i]]种方法
            //例如j=20，volume=10，而有5种方法能装满体积为10的口袋，那么只要有体积为10的物体就一定多出5种装满体积为20的口袋的方法
            dp[volume[i]]++;//显而易见，当口袋体积等于该物体体积时，必然有一种方法
        }             //而可能不止一个物体有这样的体积，所以每次碰到这个体积的物体，就做一次++运算
        printf("%d\n",dp[40]);
    }//while
    return 0;
}

#include <stdio.h>
#define N 801

int main()
{
    int a, n;
    int method[N];//method[i]表示i有几种凑法
    while(scanf("%d", &n)!=EOF)
    {
        for(int i=0; i<N; i++)
        {
            method[i]=0;
        }
        method[0]=1;
        for(int i=0; i<n; i++)
        {
            scanf("%d", &a);
            for(int j=N-1; j>=a; j--)
            {
                method[j]+=method[j-a];
            }
        }
        printf("%d\n", method[40]);
    }
    return 0;
}

#include<iostream>
using namespace std;
//方法一：递归
int count(int n, int*& a, int i, int sum)
{
	if (sum == 0)
		return 1; //找到一组和为sum的组合数；
	if (i == n || sum < 0)
		return 0;//i==n说明没有其他的数来组合，sum<0说明组合不出;
	//从数组的第i为开始，包含a[i],和不包含a[i];
	return count(n, a, i + 1, sum - a[i]) + count(n, a, i + 1, sum);
}
void recursion(int n)//递归
{
	int* a = new int[n];
	for (int i = 0; i < n; i++)
		cin >> a[i];
	cout << count(n, a, 0, 40) << endl;
	delete[] a;
}
//法二:动态规划，对物品组成的体积进行动态规划。
void dynamic(int n)
{
	int* a = new int[n + 1];
	int(*dp)[41] = new int[n + 1][41];//dp[i][j]表示从前i个物品中凑出体积j；
	for (int i = 0; i < 41; i++)
		dp[0][i] = 0;//初始边界:从前0个里凑不出任何体积
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		dp[i][0] = 1; //初始边界:随便从前几个都能凑出0体积
	}
	dp[0][0] = 1;//初始边界:0可以凑出0
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= 40; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (a[i] <= j)
				dp[i][j] += dp[i - 1][j - a[i]];
		}
	cout << dp[n][40] << endl;
	delete[] a, dp;
}
//法三:动态规划，对容积的可达性进行动态规划。
void dynamic_2(int n)
{
	int a;
	int* dp = new int[41];//dp[i]表示凑出体积i的次数；
	for (int i = 1; i <= 40; i++)
		dp[i] = 0;//初始边界：开始所有体积都没被凑出
	for (int i = 1; i <= n; i++)
	{
		cin >> a;
		for (int j = 40; j >= 1; j--) //逆序，否则要重复更新
			if (dp[j] > 0 && j + a <= 40)
				dp[j + a] += dp[j];//如果j有dp[j]种方式可达，则每种方式加上a就可达j+a
		dp[a]++;
	}
	cout << dp[40] << endl;
	delete[] dp;
}
int main()
{
	int n;
	while (cin >> n)
	{
		//recursion(n);
		//dynamic(n);
		dynamic_2(n);
	}
	return 0;
}

#!/usr/bin/python
#-*- coding:utf-8 -*-

#Author: Ben

while True:
    try:
        N = input()
        ways = [0]*41
        ways[0] = 1
        for i in range(N):
            weight = input()
            num = 40 - weight
            while num >= 0:
                if ways[num]:
                    ways[num+weight] += ways[num]
                num -= 1
        print ways[40]
    except:
        break 

#include <bits/stdc++.h>
/*
    深度搜索，我们如果找到一个解，那么直接种类加一，返回
*/
using namespace std;
const int MAXN = 25;
const int total = 40; // 总重量
bool visit[MAXN]; // 标记数组
int matter[MAXN]; // 存放物品
int kind = 0; // 记录一共有多少种
int n; // 物品的数量

void DFS(int sum,int position) { // sum为当前已经凑的质量
	if(sum==total) {
		kind++; // 种数增加
		return;
	}
	// 从第一件开始凑数
	for(int i=position; i<n; i++) {
		if(visit[i] || sum+matter[i]>total) {
			continue;
		}
		visit[i] = true;
		DFS(sum+matter[i],i);
		visit[i] = false; // 回溯
	}
}

int main() {
	cin>>n;
	int sum = 0; // 记录所有物品的质量总和
	for(int i=0; i<n; i++) {
		cin>>matter[i];
		sum+=matter[i];
	}
	sort(matter,matter+n);
	// 总和小于40或者最大的已经大于40了
	if(sum<40 || matter[0]>40) {
		cout<<kind<<endl;
		return 0;
	} else {
		memset(visit,false,sizeof(visit));
		DFS(0,0);
		cout<<kind<<endl;
	}
	return 0;
}

	#include <iostream>



	#include <cstring>



	#include <cstdio>



	



	using namespace std;



	#define N 100



	inta[N],n;



	int ways(int n,int w)



	{



	if(w==0) return 1;



	if(n<=0) return 0;



	return ways(n-1,w)+ways(n-1,w-a[n]);



	}



	int main()



	{



	cin>>n;



	for(inti=1;i<=n;i++)



	cin>>a[i];



	cout<<ways(n,40)<<endl;



	return0;



	}

import java.util.Scanner;

public class Main1 {
    static int count=0;//表示有多少种
    static int[] arr; //表示口袋
    static int n;//表示物品的种类
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        while(input.hasNext()){
            n=input.nextInt();
            arr=new int[n+1];
            /*这里的大小我们设置的比物品的种类要大1，因为在下边进行递归的时候，
            如果大小为n,因为在放第一个的时候还要考虑第一个的前一个（倒着放的：相对正着放方便一点），
            数组大小为n的话会造成数组溢出
             */
            for(int i=1;i<=n;i++){
                arr[i]=input.nextInt();
            }
        }
        count(40,n);
        System.out.println(count);
    }
    public static void count(int s,int n){
        /**
         * s表示背包剩下的容量大小
         * n表示剩下的东西数量
         */
        //如果背包容量刚好等于零，说明刚好装满
        if(s==0){
            count++;
        }
        //背包容量小于零或者容量大于零但是东西数量小于零，则不能刚好装满（也就是要么装不下了要么不够装了）
        if(s<=0||(s>0&&n<0)){
            return ;
        }
        //从最后一个开始装
        count(s-arr[n],n-1);
        //如果最后一个和其他是都值完了，从倒数第二个开始
        count(s,n-1);
    }
}
————————————————
版权声明：本文为CSDN博主「峰回路转」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44840148/article/details/104704883

python解法：使用dfs来做的。

def dfs(arr,vol):
    global res
    if vol<0:
        return
    if vol==0:
        res+=1
        return
    for i,v in enumerate(arr):
        dfs(arr[i+1:],vol-v)
while True:
    try:
        a, arr = int(input()), []
        for i in range(a):
            arr.append(int(input()))
        res=0
        dfs(arr,40)
        print(res)
    except:
        break

不过这种解法对于这道题来说是可以的，因为给的数量比较小。如果是比较大的数组就GG了。DP才是正路子啊

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 21;

int v[maxn];        // 存储每个物品体积
int bite[maxn];     // 用于标记这个物品是否出现在最后的队列中

int count = 0;      // 计数器
int total = 0;      // 物品总数量

/**
    num : 现在要放第几个物品， num >= 0
    n : 剩余容积
*/
void solve(int num, int n)
{
    if(n == 0)
    {
        // 没有剩余容积则是一种方法
        ++count;
        return ;
    }

    if(num == total)
    {
        // 放到最后也没有结束
        return ;
    }

    bite[num] = 1;
    solve(num+1, n-v[num]);
    bite[num] = 0;
    solve(num+1, n);

}

int main()
{
    
    cin >> total;
    for(int i = 0; i < total; ++i)
    {
        cin >> v[i];
    }

    solve(0, 40);

    cout << count ;

    return 0;
}