此题的第一个想法依然是搜索．也就是在这个集合里面，挑出一个真子集，使得该子集的平均值，等于targetAvg（也就是整个集合的平均数）。
这种搜索是要遍历每个元素的两种选择：是否放在这个子集中，最坏情况是需要把所有的分类情况都列举完全才能得到最后结果（比如要判定结论是false的话），那么时间复杂度就达到了o(2^N)级别，所以这是NP问题．对于NP问题的搜索解法，我们只能寄希望于高效的剪枝来减少搜索范围，但需要注意一般而言剪枝并不能从根本上改变时间复杂度．
我们将数组从小到大拍之后，能想到的这么几个优化剪枝的条件：
-
如果当前已选择的子集元素的平均值太小，即使加上后面全部的元素也没法提升到targetAvg，可以提前退出。
-
如果当前已选择的子集元素的平均值太大，已经超过了targetAvg，可以提前退出。
-
如果当前idx开始有若干个连续的元素都是相等的：要么选择将这个元素加入子集中，然后递归处理下一个元素(idx+1)；要么选择不将这个元素加入子集中，然后机柜处理下一个不同的元素(A[i]!=A[idx])。
可惜结果仍然是TLE。
我们考虑一个合法的真子集的元素个数是num，元素总和是sum，因为这个子集的平均数和整体的平均数相等，所以我们有
total/n = sum/num
转换一下
total * num = sum * n
可以发现{sum,num}是需要有制约关系的，而且不是任意的num都会有一个整数的sum对应。考虑到num最多也就是30个，所以这样的pair最多30个（事实上由于二者的整除关系，符合条件的配对肯定更少）。我们尝试遍历这些pair，将题目转化为：查看数组里是否能有一个真子集，元素个数是num，元素的总数是sum。
这看上去又是一个常规的DFS，而且也是o(2^n)的复杂度。DFS的过程中，我们遍历每一个元素A[idx]，有两种选择：不取它加入子集，于是递归处理下一个元素idx+1；取它加入子集，同时num-=1以及sum-=A[idx]，然后递归处理下一个元素。
搜索的截止条件有这么几个：
-
当恰好num==0且sum==0的时候，返回true
-
当num或者sum有任意一个先小于等于零的时候，返回false
-
idx已经处理到头了仍未满足条件，返回false.
解法1中的第三个剪枝条件也可以用上。事实上这个暴力搜索的代码跑得非常快。可能是因为上面条件2的触发概率很高。
大家都知道，DP就等于记忆化搜索。解法2给了我们一个提示，就是找寻一个真子集满足如下条件的sum和num配对即可：
total * num = sum * n (1)
于是我们定义状态变量dp[sum][num]来表示一个布尔值：是否可能存在这样的一个子集使得它们的元素和是sum，个数是num。我们可以联想到背包问题：我们依次遍历当前的元素A[i]=a，如果dp[sum-a][num-1]存在，那么就说明dp[sum][num]存在。对于任何dp[sum][num]为真的sum和num，如果满足上面的关系式就可以返回true。
注意在背包问题中，这一轮的dp状态取决于的是上一轮的dp状态（也就是说对应的A[i]不同）。如果在本轮中dp[sum-a][num-1]已经被修改了，那么在更新dp[sum][num]的结果就会出现错误。解决方法是再开一个数组储存之前的状态auto temp=dp，或者是将sum和num都从大到小遍历。这样在同一轮里，更新dp[sum][num]的时候dp[sum-a][num-1]肯定还没有更新。
这样的时间复杂度是o(N*N*Sum).
上述的DP算法仍然不是很快，主要是这个二维DP的遍历右点麻烦。这里有一个非常优秀的解法，我们可以优化dp[sum][num]的储存。原先这个状态变量储存的只是一个bool值，有些浪费。现在我们定义dp[sum]表示一个二进制整数，其中从低到高第i位bit是1的话，就表示存在一个真子集，使得元素和为sum，元素个数是i。
也就是说，如果dp[sum][num]=b01010010，那么就等效于解法3中的dp[sum][1]=true,dp[sum][4]=true和dp[sum][6]=true，
算法的框架和解法3一样，也是一个背包问题。我们遍历所有的元素A[i]=a，此时考虑加入元素a之后，dp[sum]就取决于取决于dp[sum-a]。对于所有子集元素和是sum-a的方案，只要再加上一个元素a就可以实现子集元素和是sum。因此我们有这么一个表达式：
dp[sum] |= dp[sum-a]
我们在有了dp[sum]之后，就可以知道对应的有哪些num了，逐个判断一下那个num和sum满足表达式(1)，就可以返回true。更高效的方法根据sum和表达式(1)，直接求出对应的num（而且必须是整数），然后查看dp[sum]里面对应那一位bit是否为1.