the-number-of-beautiful-subsets

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 an array <code>nums</code> of positive integers and a positive integer <code>k</code>.

A subset of <code>nums</code> is beautiful if it does not contain two integers with an absolute difference equal to <code>k</code>.

Return the number of non-empty beautiful subsets of the array <code>nums</code>.

A subset of <code>nums</code> is an array that can be obtained by deleting some (possibly none) elements from <code>nums</code>. Two subsets are different if and only if the chosen indices to delete are different.

&nbsp;
Example 1:

<pre>
Input: nums = [2,4,6], k = 2
Output: 4
Explanation: The beautiful subsets of the array nums are: [2], [4], [6], [2, 6].
It can be proved that there are only 4 beautiful subsets in the array [2,4,6].
</pre>

Example 2:

<pre>
Input: nums = [1], k = 1
Output: 1
Explanation: The beautiful subset of the array nums is [1].
It can be proved that there is only 1 beautiful subset in the array [1].
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 18</code></li>
	<li><code>1 &lt;= nums[i], k &lt;= 1000</code></li>
</ul>

beautifulSubsets

The Number of Beautiful Subsets

Construct the Lexicographically Largest Valid Sequence

construct-the-lexicographically-largest-valid-sequence

构建字典序最大的可行序列

Array

Hash Table

Math

Dynamic Programming

Backtracking

Combinatorics

Sorting

给你一个由正整数组成的数组 <code>nums</code> 和一个 正 整数 <code>k</code> 。

如果 <code>nums</code> 的子集中，任意两个整数的绝对差均不等于 <code>k</code> ，则认为该子数组是一个 美丽 子集。

返回数组 <code>nums</code> 中 非空 且 美丽 的子集数目。

<code>nums</code> 的子集定义为：可以经由 <code>nums</code> 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

&nbsp;

示例 1：

<pre>
输入：nums = [2,4,6], k = 2
输出：4
解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。
</pre>

示例 2：

<pre>
输入：nums = [1], k = 1
输出：1
解释：数组 nums 中的美丽数组有：[1] 。
可以证明数组 [1] 中只存在 1 个美丽子集。 
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 18</code></li>
	<li><code>1 &lt;= nums[i], k &lt;= 1000</code></li>
</ul>