count-of-sub-multisets-with-bounded-sum

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed array <code>nums</code> of non-negative integers, and two integers <code>l</code> and <code>r</code>.

Return the count of sub-multisets within <code>nums</code> where the sum of elements in each subset falls within the inclusive range of <code>[l, r]</code>.

Since the answer may be large, return it modulo <code>109 + 7</code>.

A sub-multiset is an unordered collection of elements of the array in which a given value <code>x</code> can occur <code>0, 1, ..., occ[x]</code> times, where <code>occ[x]</code> is the number of occurrences of <code>x</code> in the array.

Note that:

<ul>
	<li>Two sub-multisets are the same if sorting both sub-multisets results in identical multisets.</li>
	<li>The sum of an empty multiset is <code>0</code>.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: nums = [1,2,2,3], l = 6, r = 6
Output: 1
Explanation: The only subset of nums that has a sum of 6 is {1, 2, 3}.
</pre>

Example 2:

<pre>
Input: nums = [2,1,4,2,7], l = 1, r = 5
Output: 7
Explanation: The subsets of nums that have a sum within the range [1, 5] are {1}, {2}, {4}, {2, 2}, {1, 2}, {1, 4}, and {1, 2, 2}.
</pre>

Example 3:

<pre>
Input: nums = [1,2,1,3,5,2], l = 3, r = 5
Output: 9
Explanation: The subsets of nums that have a sum within the range [3, 5] are {3}, {5}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {1, 1, 2}, {1, 1, 3}, and {1, 2, 2}.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 104</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2 * 104</code></li>
	<li>Sum of <code>nums</code> does not exceed <code>2 * 104</code>.</li>
	<li><code>0 &lt;= l &lt;= r &lt;= 2 * 104</code></li>
</ul>

countSubMultisets

Count of Sub-Multisets With Bounded Sum

Coin Change

coin-change

零钱兑换

Coin Change II

coin-change-ii

零钱兑换 II

Array

Hash Table

Dynamic Programming

Sliding Window

给你一个下标从 0&nbsp;开始的非负整数数组&nbsp;<code>nums</code>&nbsp;和两个整数&nbsp;<code>l</code> 和&nbsp;<code>r</code>&nbsp;。

请你返回&nbsp;<code>nums</code>&nbsp;中子多重集合的和在闭区间&nbsp;<code>[l, r]</code>&nbsp;之间的 子多重集合的数目 。

由于答案可能很大，请你将答案对&nbsp;<code>109 + 7</code>&nbsp;取余后返回。

子多重集合 指的是从数组中选出一些元素构成的 无序&nbsp;集合，每个元素 <code>x</code>&nbsp;出现的次数可以是&nbsp;<code>0, 1, ..., occ[x]</code>&nbsp;次，其中&nbsp;<code>occ[x]</code>&nbsp;是元素&nbsp;<code>x</code>&nbsp;在数组中的出现次数。

注意：

<ul>
	<li>如果两个子多重集合中的元素排序后一模一样，那么它们两个是相同的&nbsp;子多重集合&nbsp;。</li>
	<li>空&nbsp;集合的和是 <code>0</code>&nbsp;。</li>
</ul>

&nbsp;

示例 1：

<pre>
输入：nums = [1,2,2,3], l = 6, r = 6
输出：1
解释：唯一和为 6 的子集合是 {1, 2, 3} 。
</pre>

示例 2：

<pre>
输入：nums = [2,1,4,2,7], l = 1, r = 5
输出：7
解释：和在闭区间 [1, 5] 之间的子多重集合为 {1} ，{2} ，{4} ，{2, 2} ，{1, 2} ，{1, 4} 和 {1, 2, 2} 。
</pre>

示例 3：

<pre>
输入：nums = [1,2,1,3,5,2], l = 3, r = 5
输出：9
解释：和在闭区间 [3, 5] 之间的子多重集合为 {3} ，{5} ，{1, 2} ，{1, 3} ，{2, 2} ，{2, 3} ，{1, 1, 2} ，{1, 1, 3} 和 {1, 2, 2} 。</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 104</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2 * 104</code></li>
	<li><code>nums</code> 的和不超过&nbsp;<code>2 * 104</code> 。</li>
	<li><code>0 &lt;= l &lt;= r &lt;= 2 * 104</code></li>
</ul>