Readme

2597.The-Number-of-Beautiful-Subsets

解法1：

看到数据规模nums.size()<=20，最多2^20种组合数目，意味着暴力枚举即可。一个DFS即可解决。

解法2：

本题有o(N)的解法。我们将所有的数字按照对k取模分类。对于位于不同类的数字，彼此之间是否选取都是没有制约关系的。也就是说，假设第一类数字里我们有k1种选法，第一类数字里我们有k2种选法，...，那么最终的答案就是k1*k2*....

对于同一类的数字，我们将其去重并从小到大排序之后，相邻元素之间的差值必然是k的整数倍。此时的问题转化为：总共有多少种元素的取法，要求相邻元素如果恰好相差k的话不能同时取。这就是典型的house robber问题。我们维护两个变量：take表示假设当前元素被选取的话，有多少种组合方法；notake表示当前元素不被选取的话，有多少种方法。于是

if (当前元素与前一个元素恰好相差k)
{
  take = notake * 当前元素的个数;
  nottake = (take+notake) * 1;
}
else
{
  take = (take+notake) * 当前元素的个数;
  nottake = (take+notake) * 1;
}

最终返回take+notake就是该类数字里总共合法的组合数目。

注意，最终相乘之后的答案要减去“空集”这种情况。