Problem: 805. Split Array With Same Average 数组的均值分割
解题过程
深度优先搜索，回溯，只需要考虑一个数组即可，若avg = 1.5, 数组长度11 则 11x1.4 = 3 x 1.5 + 8 * 1.5，所以只需要考虑一个数组，拿到平均值，然后avg * i，若是整数则证明可行的，拿到最大的i索引，然后dfs，若已经找到或者个数>mx（最大的索引i）返回，若哈希表中有这个项则返回，同一步需要去重的，否则会超时，也就是递归的同一层不能是同一个数字，也就是pre!=nums[i]
Code
class Solution { public: unordered_map<int, double> ump; bool flag = false; int mx; bool status[10002]; void dfs(vector<int>& nums, int index, int steps, double sum) { if(flag == true || steps > mx) return; if(steps < nums.size() && ump.find(steps)!=ump.end() && ump[steps]-sum ==0.0) { flag = true; return; } int pre = -1; for(int i = index; i < nums.size(); i++) { if(nums[i] == pre) continue; dfs(nums, i + 1, steps + 1, sum + nums[i]); pre = nums[i]; } } bool splitArraySameAverage(vector<int>& nums) { int sum = 0; sort(nums.begin(), nums.end()); for(int& i : nums) sum += i; memset(status, 0, sizeof(status)); double avg = sum / (double) nums.size(), tmp; for(int i = 1; i <= nums.size() - 1; i++) { tmp = avg * (double)i; if(tmp - (int)tmp < 1e-10) { mx = i; ump[i] = (double)(int)tmp; } } if(ump.size() == 0) return false; dfs(nums, 0, 0, 0.0); return flag; } };
