Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2597.html
2597. The Number of Beautiful Subsets
Description
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
Solutions
Solution 1: Counting + Backtracking
We use a hash table or an array $cnt$ to record the currently selected numbers and their counts, and use $ans$ to record the number of beautiful subsets, initially $ans = -1$, indicating that the empty set is excluded.
For each number $x$ in the array $nums$, we have two choices:
- Do not choose $x$, and then directly recurse to the next number;
- Choose $x$, then we need to check whether $x + k$ and $x - k$ have appeared in $cnt$ before, if neither has appeared before, then we can choose $x$, at this time we add one to the number of $x$, and then recurse to the next number, and finally subtract one from the number of $x$.
Finally, we return $ans$.
Time complexity $O(2^n)$, space complexity $O(n)$, where $n$ is the length of the array $nums$.
-
class Solution { private int[] nums; private int[] cnt = new int[1010]; private int ans = -1; private int k; public int beautifulSubsets(int[] nums, int k) { this.k = k; this.nums = nums; dfs(0); return ans; } private void dfs(int i) { if (i >= nums.length) { ++ans; return; } dfs(i + 1); boolean ok1 = nums[i] + k >= cnt.length || cnt[nums[i] + k] == 0; boolean ok2 = nums[i] - k < 0 || cnt[nums[i] - k] == 0; if (ok1 && ok2) { ++cnt[nums[i]]; dfs(i + 1); --cnt[nums[i]]; } } }
-
class Solution { public: int beautifulSubsets(vector<int>& nums, int k) { int ans = -1; int cnt[1010]{}; int n = nums.size(); function<void(int)> dfs = [&](int i) { if (i >= n) { ++ans; return; } dfs(i + 1); bool ok1 = nums[i] + k >= 1010 || cnt[nums[i] + k] == 0; bool ok2 = nums[i] - k < 0 || cnt[nums[i] - k] == 0; if (ok1 && ok2) { ++cnt[nums[i]]; dfs(i + 1); --cnt[nums[i]]; } }; dfs(0); return ans; } };
-
class Solution: def beautifulSubsets(self, nums: List[int], k: int) -> int: def dfs(i: int) -> None: nonlocal ans if i >= len(nums): ans += 1 return dfs(i + 1) if cnt[nums[i] + k] == 0 and cnt[nums[i] - k] == 0: cnt[nums[i]] += 1 dfs(i + 1) cnt[nums[i]] -= 1 ans = -1 cnt = Counter() dfs(0) return ans
-
func beautifulSubsets(nums []int, k int) int { ans := -1 n := len(nums) cnt := [1010]int{} var dfs func(int) dfs = func(i int) { if i >= n { ans++ return } dfs(i + 1) ok1 := nums[i]+k >= len(cnt) || cnt[nums[i]+k] == 0 ok2 := nums[i]-k < 0 || cnt[nums[i]-k] == 0 if ok1 && ok2 { cnt[nums[i]]++ dfs(i + 1) cnt[nums[i]]-- } } dfs(0) return ans }
-
function beautifulSubsets(nums: number[], k: number): number { let ans: number = -1; const cnt: number[] = new Array(1010).fill(0); const n: number = nums.length; const dfs = (i: number) => { if (i >= n) { ++ans; return; } dfs(i + 1); const ok1: boolean = nums[i] + k >= 1010 || cnt[nums[i] + k] === 0; const ok2: boolean = nums[i] - k < 0 || cnt[nums[i] - k] === 0; if (ok1 && ok2) { ++cnt[nums[i]]; dfs(i + 1); --cnt[nums[i]]; } }; dfs(0); return ans; }