The Number of Beautiful Subsets — LeetCode 2597 Python Solution

The problem

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.

Example

Input

nums = [2,4,6], k = 2

Output

4

Explanation

The beautiful subsets of the array nums are: [2], [4], [6], [2, 6].

Python solution

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

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2597. The Number of Beautiful Subsets is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems