bowang0911/leetcode huggingface dataset:
Count Ways to Group Overlapping Ranges

You are given a 2D integer array `ranges` where `ranges[i] = [starti, endi]` denotes that all integers between `starti` and `endi` (both **inclusive**) are contained in the `ith` range.

You are to split `ranges` into **two** (possibly empty) groups such that:

*   Each range belongs to exactly one group.
*   Any two **overlapping** ranges must belong to the **same** group.

Two ranges are said to be **overlapping** if there exists at least **one** integer that is present in both ranges.

*   For example, `[1, 3]` and `[2, 5]` are overlapping because `2` and `3` occur in both ranges.

Return _the **total number** of ways to split_ `ranges` _into two groups_. Since the answer may be very large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** ranges = \[\[6,10\],\[5,15\]\]
**Output:** 2
**Explanation:** 
The two ranges are overlapping, so they must be in the same group.
Thus, there are two possible ways:
- Put both the ranges together in group 1.
- Put both the ranges together in group 2.

**Example 2:**

**Input:** ranges = \[\[1,3\],\[10,20\],\[2,5\],\[4,8\]\]
**Output:** 4
**Explanation:** 
Ranges \[1,3\], and \[2,5\] are overlapping. So, they must be in the same group.
Again, ranges \[2,5\] and \[4,8\] are also overlapping. So, they must also be in the same group. 
Thus, there are four possible ways to group them:
- All the ranges in group 1.
- All the ranges in group 2.
- Ranges \[1,3\], \[2,5\], and \[4,8\] in group 1 and \[10,20\] in group 2.
- Ranges \[1,3\], \[2,5\], and \[4,8\] in group 2 and \[10,20\] in group 1.

**Constraints:**

*   `1 <= ranges.length <= 105`
*   `ranges[i].length == 2`
*   `0 <= starti <= endi <= 109`
Count Number of Possible Root Nodes

Alice has an undirected tree with `n` nodes labeled from `0` to `n - 1`. The tree is represented as a 2D integer array `edges` of length `n - 1` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree.

Alice wants Bob to find the root of the tree. She allows Bob to make several **guesses** about her tree. In one guess, he does the following:

*   Chooses two **distinct** integers `u` and `v` such that there exists an edge `[u, v]` in the tree.
*   He tells Alice that `u` is the **parent** of `v` in the tree.

Bob's guesses are represented by a 2D integer array `guesses` where `guesses[j] = [uj, vj]` indicates Bob guessed `uj` to be the parent of `vj`.

Alice being lazy, does not reply to each of Bob's guesses, but just says that **at least** `k` of his guesses are `true`.

Given the 2D integer arrays `edges`, `guesses` and the integer `k`, return _the **number of possible nodes** that can be the root of Alice's tree_. If there is no such tree, return `0`.

**Example 1:**

**Input:** edges = \[\[0,1\],\[1,2\],\[1,3\],\[4,2\]\], guesses = \[\[1,3\],\[0,1\],\[1,0\],\[2,4\]\], k = 3
**Output:** 3
**Explanation:** 
Root = 0, correct guesses = \[1,3\], \[0,1\], \[2,4\]
Root = 1, correct guesses = \[1,3\], \[1,0\], \[2,4\]
Root = 2, correct guesses = \[1,3\], \[1,0\], \[2,4\]
Root = 3, correct guesses = \[1,0\], \[2,4\]
Root = 4, correct guesses = \[1,3\], \[1,0\]
Considering 0, 1, or 2 as root node leads to 3 correct guesses.

**Example 2:**

**Input:** edges = \[\[0,1\],\[1,2\],\[2,3\],\[3,4\]\], guesses = \[\[1,0\],\[3,4\],\[2,1\],\[3,2\]\], k = 1
**Output:** 5
**Explanation:** 
Root = 0, correct guesses = \[3,4\]
Root = 1, correct guesses = \[1,0\], \[3,4\]
Root = 2, correct guesses = \[1,0\], \[2,1\], \[3,4\]
Root = 3, correct guesses = \[1,0\], \[2,1\], \[3,2\], \[3,4\]
Root = 4, correct guesses = \[1,0\], \[2,1\], \[3,2\]
Considering any node as root will give at least 1 correct guess. 

**Constraints:**

*   `edges.length == n - 1`
*   `2 <= n <= 105`
*   `1 <= guesses.length <= 105`
*   `0 <= ai, bi, uj, vj <= n - 1`
*   `ai != bi`
*   `uj != vj`
*   `edges` represents a valid tree.
*   `guesses[j]` is an edge of the tree.
*   `guesses` is unique.
*   `0 <= k <= guesses.length`
Pass the Pillow

There are `n` people standing in a line labeled from `1` to `n`. The first person in the line is holding a pillow initially. Every second, the person holding the pillow passes it to the next person standing in the line. Once the pillow reaches the end of the line, the direction changes, and people continue passing the pillow in the opposite direction.

*   For example, once the pillow reaches the `nth` person they pass it to the `n - 1th` person, then to the `n - 2th` person and so on.

Given the two positive integers `n` and `time`, return _the index of the person holding the pillow after_ `time` _seconds_.

**Example 1:**

**Input:** n = 4, time = 5
**Output:** 2
**Explanation:** People pass the pillow in the following way: 1 -> 2 -> 3 -> 4 -> 3 -> 2.
Afer five seconds, the pillow is given to the 2nd person.

**Example 2:**

**Input:** n = 3, time = 2
**Output:** 3
**Explanation:** People pass the pillow in the following way: 1 -> 2 -> 3.
Afer two seconds, the pillow is given to the 3rd person.

**Constraints:**

*   `2 <= n <= 1000`
*   `1 <= time <= 1000`
Kth Largest Sum in a Binary Tree

You are given the `root` of a binary tree and a positive integer `k`.

The **level sum** in the tree is the sum of the values of the nodes that are on the **same** level.

Return _the_ `kth` _**largest** level sum in the tree (not necessarily distinct)_. If there are fewer than `k` levels in the tree, return `-1`.

**Note** that two nodes are on the same level if they have the same distance from the root.

**Example 1:**

**Input:** root = \[5,8,9,2,1,3,7,4,6\], k = 2
**Output:** 13
**Explanation:** The level sums are the following:
- Level 1: 5.
- Level 2: 8 + 9 = 17.
- Level 3: 2 + 1 + 3 + 7 = 13.
- Level 4: 4 + 6 = 10.
The 2nd largest level sum is 13.

**Example 2:**

**Input:** root = \[1,2,null,3\], k = 1
**Output:** 3
**Explanation:** The largest level sum is 3.

**Constraints:**

*   The number of nodes in the tree is `n`.
*   `2 <= n <= 105`
*   `1 <= Node.val <= 106`
*   `1 <= k <= n`
Split the Array to Make Coprime Products

You are given a **0-indexed** integer array `nums` of length `n`.

A **split** at an index `i` where `0 <= i <= n - 2` is called **valid** if the product of the first `i + 1` elements and the product of the remaining elements are coprime.

*   For example, if `nums = [2, 3, 3]`, then a split at the index `i = 0` is valid because `2` and `9` are coprime, while a split at the index `i = 1` is not valid because `6` and `3` are not coprime. A split at the index `i = 2` is not valid because `i == n - 1`.

Return _the smallest index_ `i` _at which the array can be split validly or_ `-1` _if there is no such split_.

Two values `val1` and `val2` are coprime if `gcd(val1, val2) == 1` where `gcd(val1, val2)` is the greatest common divisor of `val1` and `val2`.

**Example 1:**

**Input:** nums = \[4,7,8,15,3,5\]
**Output:** 2
**Explanation:** The table above shows the values of the product of the first i + 1 elements, the remaining elements, and their gcd at each index i.
The only valid split is at index 2.

**Example 2:**

**Input:** nums = \[4,7,15,8,3,5\]
**Output:** -1
**Explanation:** The table above shows the values of the product of the first i + 1 elements, the remaining elements, and their gcd at each index i.
There is no valid split.

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 104`
*   `1 <= nums[i] <= 106`
Number of Ways to Earn Points

There is a test that has `n` types of questions. You are given an integer `target` and a **0-indexed** 2D integer array `types` where `types[i] = [counti, marksi]` indicates that there are `counti` questions of the `ith` type, and each one of them is worth `marksi` points.

Return _the number of ways you can earn **exactly**_ `target` _points in the exam_. Since the answer may be too large, return it **modulo** `109 + 7`.

**Note** that questions of the same type are indistinguishable.

*   For example, if there are `3` questions of the same type, then solving the `1st` and `2nd` questions is the same as solving the `1st` and `3rd` questions, or the `2nd` and `3rd` questions.

**Example 1:**

**Input:** target = 6, types = \[\[6,1\],\[3,2\],\[2,3\]\]
**Output:** 7
**Explanation:** You can earn 6 points in one of the seven ways:
- Solve 6 questions of the 0th type: 1 + 1 + 1 + 1 + 1 + 1 = 6
- Solve 4 questions of the 0th type and 1 question of the 1st type: 1 + 1 + 1 + 1 + 2 = 6
- Solve 2 questions of the 0th type and 2 questions of the 1st type: 1 + 1 + 2 + 2 = 6
- Solve 3 questions of the 0th type and 1 question of the 2nd type: 1 + 1 + 1 + 3 = 6
- Solve 1 question of the 0th type, 1 question of the 1st type and 1 question of the 2nd type: 1 + 2 + 3 = 6
- Solve 3 questions of the 1st type: 2 + 2 + 2 = 6
- Solve 2 questions of the 2nd type: 3 + 3 = 6

**Example 2:**

**Input:** target = 5, types = \[\[50,1\],\[50,2\],\[50,5\]\]
**Output:** 4
**Explanation:** You can earn 5 points in one of the four ways:
- Solve 5 questions of the 0th type: 1 + 1 + 1 + 1 + 1 = 5
- Solve 3 questions of the 0th type and 1 question of the 1st type: 1 + 1 + 1 + 2 = 5
- Solve 1 questions of the 0th type and 2 questions of the 1st type: 1 + 2 + 2 = 5
- Solve 1 question of the 2nd type: 5

**Example 3:**

**Input:** target = 18, types = \[\[6,1\],\[3,2\],\[2,3\]\]
**Output:** 1
**Explanation:** You can only earn 18 points by answering all questions.

**Constraints:**

*   `1 <= target <= 1000`
*   `n == types.length`
*   `1 <= n <= 50`
*   `types[i].length == 2`
*   `1 <= counti, marksi <= 50`
Count the Number of Vowel Strings in Range

You are given a **0-indexed** array of string `words` and two integers `left` and `right`.

A string is called a **vowel string** if it starts with a vowel character and ends with a vowel character where vowel characters are `'a'`, `'e'`, `'i'`, `'o'`, and `'u'`.

Return _the number of vowel strings_ `words[i]` _where_ `i` _belongs to the inclusive range_ `[left, right]`.

**Example 1:**

**Input:** words = \[ "are ", "amy ", "u "\], left = 0, right = 2
**Output:** 2
**Explanation:** 
-  "are " is a vowel string because it starts with 'a' and ends with 'e'.
-  "amy " is not a vowel string because it does not end with a vowel.
-  "u " is a vowel string because it starts with 'u' and ends with 'u'.
The number of vowel strings in the mentioned range is 2.

**Example 2:**

**Input:** words = \[ "hey ", "aeo ", "mu ", "ooo ", "artro "\], left = 1, right = 4
**Output:** 3
**Explanation:** 
-  "aeo " is a vowel string because it starts with 'a' and ends with 'o'.
-  "mu " is not a vowel string because it does not start with a vowel.
-  "ooo " is a vowel string because it starts with 'o' and ends with 'o'.
-  "artro " is a vowel string because it starts with 'a' and ends with 'o'.
The number of vowel strings in the mentioned range is 3.

**Constraints:**

*   `1 <= words.length <= 1000`
*   `1 <= words[i].length <= 10`
*   `words[i]` consists of only lowercase English letters.
*   `0 <= left <= right < words.length`
Rearrange Array to Maximize Prefix Score

You are given a **0-indexed** integer array `nums`. You can rearrange the elements of `nums` to **any order** (including the given order).

Let `prefix` be the array containing the prefix sums of `nums` after rearranging it. In other words, `prefix[i]` is the sum of the elements from `0` to `i` in `nums` after rearranging it. The **score** of `nums` is the number of positive integers in the array `prefix`.

Return _the maximum score you can achieve_.

**Example 1:**

**Input:** nums = \[2,-1,0,1,-3,3,-3\]
**Output:** 6
**Explanation:** We can rearrange the array into nums = \[2,3,1,-1,-3,0,-3\].
prefix = \[2,5,6,5,2,2,-1\], so the score is 6.
It can be shown that 6 is the maximum score we can obtain.

**Example 2:**

**Input:** nums = \[-2,-3,0\]
**Output:** 0
**Explanation:** Any rearrangement of the array will result in a score of 0.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-106 <= nums[i] <= 106`
Count the Number of Beautiful Subarrays

You are given a **0-indexed** integer array `nums`. In one operation, you can:

*   Choose two different indices `i` and `j` such that `0 <= i, j < nums.length`.
*   Choose a non-negative integer `k` such that the `kth` bit (**0-indexed**) in the binary representation of `nums[i]` and `nums[j]` is `1`.
*   Subtract `2k` from `nums[i]` and `nums[j]`.

A subarray is **beautiful** if it is possible to make all of its elements equal to `0` after applying the above operation any number of times.

Return _the number of **beautiful subarrays** in the array_ `nums`.

A subarray is a contiguous **non-empty** sequence of elements within an array.

**Example 1:**

**Input:** nums = \[4,3,1,2,4\]
**Output:** 2
**Explanation:** There are 2 beautiful subarrays in nums: \[4,3,1,2,4\] and \[4,3,1,2,4\].
- We can make all elements in the subarray \[3,1,2\] equal to 0 in the following way:
  - Choose \[3, 1, 2\] and k = 1. Subtract 21 from both numbers. The subarray becomes \[1, 1, 0\].
  - Choose \[1, 1, 0\] and k = 0. Subtract 20 from both numbers. The subarray becomes \[0, 0, 0\].
- We can make all elements in the subarray \[4,3,1,2,4\] equal to 0 in the following way:
  - Choose \[4, 3, 1, 2, 4\] and k = 2. Subtract 22 from both numbers. The subarray becomes \[0, 3, 1, 2, 0\].
  - Choose \[0, 3, 1, 2, 0\] and k = 0. Subtract 20 from both numbers. The subarray becomes \[0, 2, 0, 2, 0\].
  - Choose \[0, 2, 0, 2, 0\] and k = 1. Subtract 21 from both numbers. The subarray becomes \[0, 0, 0, 0, 0\].

**Example 2:**

**Input:** nums = \[1,10,4\]
**Output:** 0
**Explanation:** There are no beautiful subarrays in nums.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `0 <= nums[i] <= 106`
Minimum Time to Complete All Tasks

There is a computer that can run an unlimited number of tasks **at the same time**. You are given a 2D integer array `tasks` where `tasks[i] = [starti, endi, durationi]` indicates that the `ith` task should run for a total of `durationi` seconds (not necessarily continuous) within the **inclusive** time range `[starti, endi]`.

You may turn on the computer only when it needs to run a task. You can also turn it off if it is idle.

Return _the minimum time during which the computer should be turned on to complete all tasks_.

**Example 1:**

**Input:** tasks = \[\[2,3,1\],\[4,5,1\],\[1,5,2\]\]
**Output:** 2
**Explanation:** 
- The first task can be run in the inclusive time range \[2, 2\].
- The second task can be run in the inclusive time range \[5, 5\].
- The third task can be run in the two inclusive time ranges \[2, 2\] and \[5, 5\].
The computer will be on for a total of 2 seconds.

**Example 2:**

**Input:** tasks = \[\[1,3,2\],\[2,5,3\],\[5,6,2\]\]
**Output:** 4
**Explanation:** 
- The first task can be run in the inclusive time range \[2, 3\].
- The second task can be run in the inclusive time ranges \[2, 3\] and \[5, 5\].
- The third task can be run in the two inclusive time range \[5, 6\].
The computer will be on for a total of 4 seconds.

**Constraints:**

*   `1 <= tasks.length <= 2000`
*   `tasks[i].length == 3`
*   `1 <= starti, endi <= 2000`
*   `1 <= durationi <= endi - starti + 1`
Distribute Money to Maximum Children

You are given an integer `money` denoting the amount of money (in dollars) that you have and another integer `children` denoting the number of children that you must distribute the money to.

You have to distribute the money according to the following rules:

*   All money must be distributed.
*   Everyone must receive at least `1` dollar.
*   Nobody receives `4` dollars.

Return _the **maximum** number of children who may receive **exactly**_ `8` _dollars if you distribute the money according to the aforementioned rules_. If there is no way to distribute the money, return `-1`.

**Example 1:**

**Input:** money = 20, children = 3
**Output:** 1
**Explanation:** 
The maximum number of children with 8 dollars will be 1. One of the ways to distribute the money is:
- 8 dollars to the first child.
- 9 dollars to the second child. 
- 3 dollars to the third child.
It can be proven that no distribution exists such that number of children getting 8 dollars is greater than 1.

**Example 2:**

**Input:** money = 16, children = 2
**Output:** 2
**Explanation:** Each child can be given 8 dollars.

**Constraints:**

*   `1 <= money <= 200`
*   `2 <= children <= 30`
Maximize Greatness of an Array

You are given a 0-indexed integer array `nums`. You are allowed to permute `nums` into a new array `perm` of your choosing.

We define the **greatness** of `nums` be the number of indices `0 <= i < nums.length` for which `perm[i] > nums[i]`.

Return _the **maximum** possible greatness you can achieve after permuting_ `nums`.

**Example 1:**

**Input:** nums = \[1,3,5,2,1,3,1\]
**Output:** 4
**Explanation:** One of the optimal rearrangements is perm = \[2,5,1,3,3,1,1\].
At indices = 0, 1, 3, and 4, perm\[i\] > nums\[i\]. Hence, we return 4.

**Example 2:**

**Input:** nums = \[1,2,3,4\]
**Output:** 3
**Explanation:** We can prove the optimal perm is \[2,3,4,1\].
At indices = 0, 1, and 2, perm\[i\] > nums\[i\]. Hence, we return 3.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `0 <= nums[i] <= 109`
Find Score of an Array After Marking All Elements

You are given an array `nums` consisting of positive integers.

Starting with `score = 0`, apply the following algorithm:

*   Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
*   Add the value of the chosen integer to `score`.
*   Mark **the chosen element and its two adjacent elements if they exist**.
*   Repeat until all the array elements are marked.

Return _the score you get after applying the above algorithm_.

**Example 1:**

**Input:** nums = \[2,1,3,4,5,2\]
**Output:** 7
**Explanation:** We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements: \[2,1,3,4,5,2\].
- 2 is the smallest unmarked element, so we mark it and its left adjacent element: \[2,1,3,4,5,2\].
- 4 is the only remaining unmarked element, so we mark it: \[2,1,3,4,5,2\].
Our score is 1 + 2 + 4 = 7.

**Example 2:**

**Input:** nums = \[2,3,5,1,3,2\]
**Output:** 5
**Explanation:** We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements: \[2,3,5,1,3,2\].
- 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element: \[2,3,5,1,3,2\].
- 2 is the only remaining unmarked element, so we mark it: \[2,3,5,1,3,2\].
Our score is 1 + 2 + 2 = 5.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 106`
Minimum Time to Repair Cars

You are given an integer array `ranks` representing the **ranks** of some mechanics. ranksi is the rank of the ith mechanic. A mechanic with a rank `r` can repair n cars in `r * n2` minutes.

You are also given an integer `cars` representing the total number of cars waiting in the garage to be repaired.

Return _the **minimum** time taken to repair all the cars._

**Note:** All the mechanics can repair the cars simultaneously.

**Example 1:**

**Input:** ranks = \[4,2,3,1\], cars = 10
**Output:** 16
**Explanation:** 
- The first mechanic will repair two cars. The time required is 4 \* 2 \* 2 = 16 minutes.
- The second mechanic will repair two cars. The time required is 2 \* 2 \* 2 = 8 minutes.
- The third mechanic will repair two cars. The time required is 3 \* 2 \* 2 = 12 minutes.
- The fourth mechanic will repair four cars. The time required is 1 \* 4 \* 4 = 16 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​

**Example 2:**

**Input:** ranks = \[5,1,8\], cars = 6
**Output:** 16
**Explanation:** 
- The first mechanic will repair one car. The time required is 5 \* 1 \* 1 = 5 minutes.
- The second mechanic will repair four cars. The time required is 1 \* 4 \* 4 = 16 minutes.
- The third mechanic will repair one car. The time required is 8 \* 1 \* 1 = 8 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​

**Constraints:**

*   `1 <= ranks.length <= 105`
*   `1 <= ranks[i] <= 100`
*   `1 <= cars <= 106`
Number of Even and Odd Bits

You are given a **positive** integer `n`.

Let `even` denote the number of even indices in the binary representation of `n` (**0-indexed**) with value `1`.

Let `odd` denote the number of odd indices in the binary representation of `n` (**0-indexed**) with value `1`.

Return _an integer array_ `answer` _where_ `answer = [even, odd]`.

**Example 1:**

**Input:** n = 17
**Output:** \[2,0\]
**Explanation:** The binary representation of 17 is 10001. 
It contains 1 on the 0th and 4th indices. 
There are 2 even and 0 odd indices.

**Example 2:**

**Input:** n = 2
**Output:** \[0,1\]
**Explanation:** The binary representation of 2 is 10.
It contains 1 on the 1st index. 
There are 0 even and 1 odd indices.

**Constraints:**

*   `1 <= n <= 1000`
Check Knight Tour Configuration

There is a knight on an `n x n` chessboard. In a valid configuration, the knight starts **at the top-left cell** of the board and visits every cell on the board **exactly once**.

You are given an `n x n` integer matrix `grid` consisting of distinct integers from the range `[0, n * n - 1]` where `grid[row][col]` indicates that the cell `(row, col)` is the `grid[row][col]th` cell that the knight visited. The moves are **0-indexed**.

Return `true` _if_ `grid` _represents a valid configuration of the knight's movements or_ `false` _otherwise_.

**Note** that a valid knight move consists of moving two squares vertically and one square horizontally, or two squares horizontally and one square vertically. The figure below illustrates all the possible eight moves of a knight from some cell.

**Example 1:**

**Input:** grid = \[\[0,11,16,5,20\],\[17,4,19,10,15\],\[12,1,8,21,6\],\[3,18,23,14,9\],\[24,13,2,7,22\]\]
**Output:** true
**Explanation:** The above diagram represents the grid. It can be shown that it is a valid configuration.

**Example 2:**

**Input:** grid = \[\[0,3,6\],\[5,8,1\],\[2,7,4\]\]
**Output:** false
**Explanation:** The above diagram represents the grid. The 8th move of the knight is not valid considering its position after the 7th move.

**Constraints:**

*   `n == grid.length == grid[i].length`
*   `3 <= n <= 7`
*   `0 <= grid[row][col] < n * n`
*   All integers in `grid` are **unique**.
The Number of Beautiful Subsets

You are given an array `nums` of positive integers and a **positive** integer `k`.

A subset of `nums` is **beautiful** if it does not contain two integers with an absolute difference equal to `k`.

Return _the number of **non-empty beautiful** subsets of the array_ `nums`.

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

**Example 1:**

**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\].

**Example 2:**

**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\].

**Constraints:**

*   `1 <= nums.length <= 20`
*   `1 <= nums[i], k <= 1000`