2597. 美丽子集的数目（回溯算法）

#### 题目详情  #### 题目解读 1、需要的是一个子数组，可以不续 2、任意两个整数的绝对差均不等于 k（可以是同一个数相减） 3、1 <= nums.length <= 18 #### 解题思路 因为数据规模较小我们可以通过暴力枚举出所有子数组然后再判断该子数组是否符合要求即可。这时我们可以使用回溯算法进行枚举。 ###### 回溯算法 简单来说回溯算法就是当一条路走完后，退回到上一个地方去走另外一条路。针对本题来讲，我们可以维护一个数组num,先添加一个数进入到下一个搜索中，这条路搜索完后再将该数去除然后再去探索其他路。这样我们便可以枚举出所有子数组了。 #### 代码 ```c++ class Solution { public: int ans=0; void dfs(vector<int>&num,vector<int>& nums,int index,int k){ if(index>=nums.size())return; num.push_back(nums[index]); bool check=true; for(int i=0;i<num.size();i++){ for(int j=i;j>=0;j--){ if(abs(num[i]-num[j])==k){check=false;break;} } if(!check)break; } if(check)ans++; dfs(num,nums,index+1,k); num.pop_back(); dfs(num,nums,index+1,k); } int beautifulSubsets(vector<int>& nums, int k) { vector<int>num; dfs(num,nums,0,k); return ans; } }; ``` #### 代码优化 针对该题官方提示还可以用动态规划进行优化，我暂时没有想到，后续补上。 #### 完结撒花 回溯算法就那么轻松学会了。我的力扣主页：[https://leetcode.cn/u/nan-wan-bu-qiu-39/](https://leetcode.cn/u/nan-wan-bu-qiu-39/) 更多算法内容：[https://api.timeplanet.cn/documents/sort?sortId=10](https://api.timeplanet.cn/documents/sort?sortId=10)