class Solution:
    def beautifulSubsets(self, nums, k):
        n: int = len(nums)

        stack: list[tuple[int, int]] = [(0, 0)]
        # index, mask

        ans: int = 0
        while stack:
            index, mask = stack.pop()
            if index == n:
                ans += 1
            else:
                is_beautiful: bool = True
                for j in range(index):
                    if not (
                            ((1 << j) & mask) == 0
                            or
                            abs(nums[j] - nums[index]) != k
                    ):
                        is_beautiful = False
                        break
                if is_beautiful:
                    stack.append((index+1, mask+(1<<index)))
                stack.append((index+1, mask))
        return ans - 1  # remove empty subset