我们可以通过几种方式从n个元素集中选取K个元素以形成数字X？ [英] In how many ways we can pick K elements from set of n elements to form a number X?

问题描述

有一点很重要-我们可以选择任意次数
次的任何元素，但总的选择元素应等于K。

例如-如果元素集为1 2 3 5且K = 3且X = 4。

然后答案是1，因为只有一种方法可以选择3个元素，这些元素加起来等于4，而这3个元素是两个1和一个2。（1 + 1 + 2 = 4）

<一个算法可以提供很大的帮助。 ：）

解决方案

让我们考虑针对硬币找零问题的DP解决方案。
通常，长度为（Sum + 1）的数组A的条目都包含整数-表示每个单元格值的方式的数目。

简单修改-进行2D数组 A [Sum + 1] [K] ，因此 A [M] [P] 将包含多种方式用P个硬币来赚钱M。

There is one important point - We can pick any element any number of times but the total picked element should be equal to K.

For example - If set of elements is 1 2 3 5 and K = 3 and X = 4.

Then answer is 1 because there is only one way to pick 3 elements which adds upto 4 and those 3 elements are two 1's and one 2. (1+1+2 = 4)

An algorithm can greatly help. :)

解决方案

Let's consider DP solution for coin change problem. Usually entries of array A with length (Sum+1) contain integers - number of ways to make the value of every cell.

Simple modification - make 2D array A[Sum+1][K], so A[M][P] will contain number of ways to make value M using P coins.

这篇关于我们可以通过几种方式从n个元素集中选取K个元素以形成数字X？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！