第一层：1、输入 2、运算 3、输出 第二层：1、判断函数 2、输入数据 3、循环输出结果 第三层：计算 循环T组 每组判断 循环计算出多个可能和 每个可能和与k比较 相等 输出yes跳出循环 不相等 不跳出循环 比较完了，都不相等，输出no跳出循环 第四层：如何计算可能和 分组 一个相加，两个相加……以此类推 第五层：有n种药物，第一种吃了能转a[1]圈有t[1]片，第二种吃了能转a[2]圈有t[2]片，以此类推，第n种吃了能转a[n]圈有t[n]片,有人想通过吃药来转k圈（k是正整数），能否满足，能则输出yes，不能则输出no。
链接：https://www.nowcoder.com/questionTerminal/7f24eb7266ce4b0792ce8721d6259800 来源：牛客网
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。 当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。
输入描述: 输入为两行: 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000) 第二行为n个正整数Ai，以空格隔开。
输出描述: 输出所求的方案数 示例1 输入 5 15 5 5 10 2 3 输出 4
//递归会超时，只能过40%，用dp. dp[i][j]表示用前i个值组成和为j的方案个数（相比一维的，更容易理解一些） #include <iostream> #include <algorithm> using namespace std; //注意：最终结果int类型存不下，需要64位数据 //注意：dp不能放在main里，栈存不下。需要存在全局数据区 long long dp[1001][1001]; int main() { int n,sum; cin>>n>>sum; int p[1000]; for(int i = 1 ; i <= n ; i++) cin>>p[i]; //初始化dp,用前i个组成和为0的方案，只有1种，就是什么都不取，和为0； for (int i = 0 ; i < n ;i++) { dp[i][0] = 1; } //用0个元素不能组成1~sum for (int j = 1 ; j < sum ;j++) { dp[0][j] = 0; } for (int i = 1 ; i <= n ;i++) { for (int j = 0 ; j<=sum ;j++) { if(p[i]<=j) dp[i][j] = dp[i-1][j]+dp[i-1][j-p[i]]; else dp[i][j] = dp[i-1][j]; } } cout<<dp[n][sum]<<endl; return 0; }算法总结）寻找组合数，求出从整数1到n中和为m的所有组合
奋斗的小炎 2018-07-12 12:44:15 4591 收藏 分类专栏： 编程 算法与数据结构 python 版权 采用背包问题原理，仅考虑具有最大的数字n是否存在与结果集合中，考虑以下两种情形：
（1）n在集合中，剩下的n-1个数字需要组成一个和为n-m的组合；
（2）n不在集合中，剩下的n-1个数字仍需要组成和为m的组合；
由于需要给出所有的组合可能，因此是一个回溯的过程。
算法设计思路：
由于是个回溯递归的过程，因此需要首先给出递归终止条件：当需要求和的数字小于等于0或所有数字都用完了的时候，就是程序终止的时候。
用一个列表数组item存储当前的候选集合，result列表存放最终的满足条件的结果，当满足条件时，将item加入result中。
因此，回溯的代码如下：
def find_combine(item, n, m, result): if n <= 0 or m <= 0: return if n == m: result.append(item + [n]) item.append(n) find_combine(item, n-1, m-n, result) item.pop() find_combine(item, n-1, m, result)用一组数字，运行一下，这里假设n=9，m=10
if __name__ == '__main__': item = [] result = [] find_combine(item, 9, 10, result) for r in result: print(r)运行结果如下：
[9, 1] [8, 2] [7, 3] [7, 2, 1] [6, 4] [6, 3, 1] [5, 4, 1] [5, 3, 2] [4, 3, 2, 1]
