回溯

leetcode 2597. 美丽子集的数目
给你一个由正整数组成的数组nums，和一个正整数k。
如果nums中子集中，任意两个整数的绝对差均不等于k，则认为该子数组是一个美丽子集。
返回数组nums中非空且美丽的子集数目。
nums的子集定义为：可以经由nums删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

思路： 由于题目要求子集中任意两个整数的绝对差均不等于k，我们可以使用回溯算法来枚举所有的子集，然后判断是否满足条件。每个元素都是选或不选，如果不选则继续往前，如果选该元素，则需要判断是否有元素与该元素构成绝对差等于k，如果有，则不能选，反之，则可以选 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def beautifulSubsets(self, nums: List[int], k: int) -> int:
    n = len(nums)
    # 去除空集的情况
    ans = -1
    # 使用哈希加快判断速度
    cnt = defaultdict(int)
    def dfs(i: int):
        # 所有元素都遍历完了
        if i == n:
            nonlocal ans
            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

    dfs(0)
    return ans