Massive Algorithms: LeetCode 805 - Split Array With Same Average

LeetCode 805 - Split Array With Same Average

https://leetcode.com/problems/split-array-with-same-average/

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.

Note:

The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000]

https://leetcode.com/articles/split-array-with-same-average/
Approach #1: Meet in the Middle [Accepted]

First, let's get a sense of the condition that average(B) = average(C), where B, C are defined in the problem statement.

Say A (the input array) has N elements which sum to S, and B (one of the splitting sets) has K elements which sum to X. Then the equation for average(B) = average(C) becomes

\frac{X}{K} = \frac{S-X}{N-K}

. This reduces to

X(N-K) = (S-X)K

which is

\frac{X}{K} = \frac{S}{N}

. That is, average(B) = average(A).

Now, we could delete average(A) from each element A[i] without changing our choice for B. (A[i] -= mu, where mu = average(A)). This means we just want to choose a set B that sums to 0.

Trying all

2^N

sets is still too many choices, so we will create sets of sums left, right of the approximately

2^{N/2}

choices on the left and on the right separately. (That is, left is a set of sums of every powerset in the first half of A, and right is the set of sums of every powerset in the second half of A). Then, it is true if we find

0

in these powersets, or if two sums in different halves cancel out (-x in right for x in left), except for one minor detail below.

Care must be taken that we do not specify sets that would make the original B or C empty. If sleft = A[0] + A[1] + ... + A[N/2 - 1], and sright = A[N/2] + ... + A[N-1], (where A[i] was transformed to the new A[i] - average(A)) then we cannot choose both (sleft, sright). This is correct because if for example sleft was a sum reached by a strictly smaller powerset than {A[0], A[1], ..., A[N/2 - 1]}, then the difference between these sets would be non-empty and have sum 0

public boolean splitArraySameAverage(int[] A) {

int N = A.length;

int S = 0;

for (int x : A)

S += x;

if (N == 1)

return false;

int g = gcd(S, N);

Point mu = new Point(-(S / g), N / g);

// A[i] -> fracAdd(A[i], mu)

List<Point> A2 = new ArrayList();

for (int x : A)

A2.add(fracAdd(new Point(x, 1), mu));

Set<Point> left = new HashSet();

left.add(A2.get(0));

for (int i = 1; i < N / 2; ++i) {

Set<Point> left2 = new HashSet();

Point z = A2.get(i);

left2.add(z);

for (Point p : left) {

left2.add(p);

left2.add(fracAdd(p, z));

}

left = left2;

}

if (left.contains(new Point(0, 1)))

return true;

Set<Point> right = new HashSet();

right.add(A2.get(N - 1));

for (int i = N / 2; i < N - 1; ++i) {

Set<Point> right2 = new HashSet();

Point z = A2.get(i);

right2.add(z);

for (Point p : right) {

right2.add(p);

right2.add(fracAdd(p, z));

}

right = right2;

}

if (right.contains(new Point(0, 1)))

return true;

Point sleft = new Point(0, 1);

for (int i = 0; i < N / 2; ++i)

sleft = fracAdd(sleft, A2.get(i));

Point sright = new Point(0, 1);

for (int i = N / 2; i < N; ++i)

sright = fracAdd(sright, A2.get(i));

for (Point ha : left) {

Point ha2 = new Point(-ha.x, ha.y);

if (right.contains(ha2) && (!ha.equals(sleft) || !ha2.equals(sright)))

return true;

}

return false;

}

public Point fracAdd(Point A, Point B) {

int numer = A.x * B.y + B.x * A.y;

int denom = A.y * B.y;

int g = gcd(numer, denom);

numer /= g;

denom /= g;

if (denom < 0) {

numer *= -1;

denom *= -1;

}

return new Point(numer, denom);

}

public int gcd(int a, int b) {

if (b == 0)

return a;

return gcd(b, a % b);

}

X. BFS + DP
https://leetcode.com/problems/split-array-with-same-average/discuss/127863/Share-a-Java-solution-using-DP

Wrote the code after watching this video: https://www.youtube.com/watch?v=FBQbm26tSzA. Really nice explanation.

    public boolean splitArraySameAverage(int[] A) {
        int sum = 0;
        for (int i : A) sum += i;
        if (!isPossible(sum, A.length)) return false;
        
        List<Set<Integer>> ls = new ArrayList<>();
        for (int i = 0; i <= A.length / 2; i++) {
            ls.add(new HashSet<>());
        }
        ls.get(0).add(0);
        
        for (int num : A) {
            for (int i = ls.size() - 1; i > 0; i--) {
                if (ls.get(i - 1).size() > 0) {
                    for (int s : ls.get(i - 1)) ls.get(i).add(s + num);
                }
            }
        }

        for (int i = 1; i < ls.size(); i++) {
            if (sum * i % A.length == 0 && ls.get(i).contains(sum * i / A.length)) return true;
        }
        return false;
    }
    
    private boolean isPossible(int sum, int n) {
        for (int i = 1; i < n; i++) {
            if (sum * i % n == 0) return true;
        }
        return false;
    }

https://leetcode.com/problems/split-array-with-same-average/discuss/120667/C%2B%2B-Solution-with-explanation-early-termination-(Updated-for-new-test-case)

First, this problem is NP, and the worst case runtime is exponential. But the expected runtime for random input could be very fast.

If the array of size n can be splitted into group A and B with same mean, assuming A is the smaller group, then

  totalSum/n = Asum/k = Bsum/(n-k), where k = A.size() and 1 <= k <= n/2;
  Asum = totalSum*k/n, which is an integer. So we have totalSum*k%n == 0;

In general, not many k are valid.

Solution 2: early pruning + knapsack DP, O(n^3 * M) 33 ms
If there are still some k valid after early pruning by checking totalSum*k%n == 0,
we can generate all possible combination sum of k numbers from the array using DP, like knapsack problem. (Note: 1 <= k <= n/2)
Next, for each valid k, simply check whether the group sum, i.e. totalSum * k / n, exists in the kth combination sum hashset.

vector<vector<unordered_set<int>>> sums(n, vector<unordered_set<int>>(n/2+1));
sums[i][j] is all possible combination sum of j numbers from the subarray A[0, i];

Goal: sums[n-1][k], for all k in range [1, n/2]
Initial condition: sums[i][0] = {0}, 0 <= i <= n-1; sums[0][1] = {all numbers in the array};
Deduction: sums[i+1][j] = sums[i][j] "join" (sums[i][j-1] + A[i+1])
The following code uses less space but the same DP formula.
Runtime analysis:
All numbers in the array are in range [0, 10000]. Let M = 10000.
So the size of kth combination sum hashset, i.e. sums[...][k], is <= k * M;
For each number in the array, the code need loop through all combination sum hashsets, so
the total runtime is n * (1 * M + 2 * M + ... + (n/2) * M) = O(n^3 * M)

class Solution {
public:
    bool splitArraySameAverage(vector<int>& A) {
        int n = A.size(), m = n/2, totalSum = accumulate(A.begin(), A.end(), 0);
        // early pruning
        bool isPossible = false;
        for (int i = 1; i <= m && !isPossible; ++i) 
            if (totalSum*i%n == 0) isPossible = true;
        if (!isPossible) return false;
        // DP like knapsack
        vector<unordered_set<int>> sums(m+1);
        sums[0].insert(0);
        for (int num: A) {
            for (int i = m; i >= 1; --i) 
                for (const int t: sums[i-1]) 
                    sums[i].insert(t + num);
        }
        for (int i = 1; i <= m; ++i) 
            if (totalSum*i%n == 0 && sums[i].find(totalSum*i/n) != sums[i].end()) return true;
        return false;
    }
};

https://leetcode.com/problems/split-array-with-same-average/discuss/121140/DP-solution-in-C%2B%2B

same as above, use more space

    public boolean splitArraySameAverage(int[] A) {
        int sum = 0;
        for(int num : A){
            sum += num;
        }
        boolean[][] dp = new boolean[sum+1][A.length/2 + 1];
        dp[0][0] = true;
        for(int num : A){
            for(int i = sum; i >= num; i--){
                for(int j = 1; j <= A.length/2; j++){
                    dp[i][j] = dp[i][j] || dp[i-num][j - 1];
                }
            }
        }
        for (int i = 1; i <= A.length/2; ++i) 
            if (sum*i%A.length == 0 && dp[sum*i/A.length][i]) return true;
        return false;
    }

X. DP

https://leetcode.com/problems/split-array-with-same-average/discuss/121140/DP-solution-in-C%2B%2B

The DP could be described as:

dp[n][k][s] = dp[n-1][k][s] || dp[n-1][k-1][s - A[n - 1]]

where dp[n][k][s] means whether sum s could be achieved by summing up k numbers selected among the first n numbers in given array.

Notice that the dp[n & 1] stuff in my code is just for saving space (otherwise you got error), which means dp[n] in above expressio

    bool splitArraySameAverage(vector<int>& A) {
        static bool dp[2][16][300001];
        int sum = 0;
        for (int a: A) sum += a;
        
        int N = A.size();
        memset(dp, 0, sizeof(dp));
        for (int n = 0; n <= N; n++) {
            dp[n & 1][0][0] = true;
        }
        for (int n = 1; n <= N; n++) {
            for (int k = 1; k <= N/2; k++) {
                for (int s = 1; s <= sum; s++) {
                    if (s >= A[n - 1]) {
                        dp[n & 1][k][s] = dp[n-1 & 1][k][s] || dp[n-1 & 1][k-1][s - A[n - 1]];
                    } else {
                        dp[n & 1][k][s] = dp[n-1 & 1][k][s];
                    }
                }
            }
        }
        for (int k = 1; k <= N/2; k++) {
            if ((k * sum / N * N == k * sum) && dp[N & 1][k][k * sum / N]) return true;
        }
        return false;
    }

https://leetcode.com/problems/split-array-with-same-average/discuss/120830/DP-with-bitset-over-size

Using dynamic programming. Bit n of p[s] tells me whether it’s possible to build a subset of size n with sum s. Based on my NumPy version.

C++ version, gets accepted in about 35 ms (in five submissions it took 36, 47, 24, 24 and 45 ms):

bool splitArraySameAverage(vector<int>& A) {        
    int N = A.size(), S = 0;
    for (int a : A) S += a;
    int p[S+1] = {1};
    for (int a : A)
        for (int s = S - a; s >= 0; s--)
            p[s+a] |= p[s] << 1;
    for (int n = 1; n < N; n++)
        if (S*n%N == 0  &&  p[S*n/N] & (1 << n))
            return true;
    return false;
}

X. Enumerate + DFS
https://www.cnblogs.com/lightwindy/p/9847602.html
TLE, For such k, the problem transforms to "Find k sum = Asum, i.e. totalSum * k/n, from an array of size n". This subproblem is similar to LC39 combination sum, which can be solved by backtracking

Solution 1: early termination + combination sum. 5 ms Now TLE (Update)

For such k, the problem transforms to "Find k sum = Asum, i.e. totalSum * k/n, from an array of size n". This subproblem is similar to LC39 combination sum, which can be solved by backtracking.

class Solution {
public:
    bool splitArraySameAverage(vector<int>& A) {
        int n = A.size(), m = n/2, totalSum = accumulate(A.begin(), A.end(), 0);
        sort(A.rbegin(), A.rend()); // Optimization
        for (int i = 1; i <= m; ++i) 
            if (totalSum*i%n == 0 && combinationSum(A, 0, i, totalSum*i/n)) return true;
        return false;
    }
    bool combinationSum(vector<int>& nums, int idx, int k, int tar) {
        if (tar > k * nums[idx]) return false; // Optimization, A is sorted from large to small
        if (k == 0) return tar == 0;
        for (int i = idx; i <= nums.size()-k; ++i) 
            if (nums[i] <= tar && combinationSum(nums, i+1, k-1, tar-nums[i])) return true;
        return false;
    }

https://leetcode.com/problems/split-array-with-same-average/discuss/120660/Java-accepted-recursive-solution-with-explanation

We need to split A into B and C, the length of B can be [1, A.length / 2], we consider them one by one:
B should have the same mean value as A, so sumB / lenOfB = sumA / lenOfA, which is equavalent to sumB = sumA * lenOfB / lenOfA. All elements here are integers, so sumB must be an integer, this gives our first criteria (sumA * lenOfB) % A.length == 0.
Then further in function check(int[] A, int leftSum, int leftNum, int startIndex), we recursicely check if we can find lenOfB elements in A who sum up to sumB.

class Solution {    
    public boolean check(int[] A, int leftSum, int leftNum, int startIndex) {       
        if (leftNum == 0) return leftSum == 0;
        if ((A[startIndex]) > leftSum / leftNum) return false;
        for (int i = startIndex; i < A.length - leftNum + 1; i ++) {
     if (i > startIndex && A[i] == A[i - 1]) continue;
            if (check(A, leftSum - A[i], leftNum - 1, i + 1)) return true;
        }
        return false;       
    }
    
    public boolean splitArraySameAverage(int[] A) {
        if (A.length == 1) return false;
        int sumA = 0;
        for (int a: A) sumA += a;
        Arrays.sort(A);
        for (int lenOfB = 1; lenOfB <= A.length / 2; lenOfB ++) {
            if ((sumA * lenOfB) % A.length == 0) {
                if (check(A, (sumA * lenOfB) / A.length, lenOfB, 0)) return true;
            }
        }
        return false;
        
    }

https://leetcode.com/problems/split-array-with-same-average/discuss/120741/Easy-and-Concise-Solution-C%2B%2BJavaPython

Change the quesiton change to a N-sum problem:
To find if
1 element with sum = 1 * avg or
2 elements with sum = 2 * avg or
i elements with sum = i * avg

The size of smaller list between B and C will be less than N/2+1, so 0 < i < N/2+1

Recursive funciton find try to find a subset of n elements from A with sum = target

    public boolean splitArraySameAverage(int[] A) {
        int n = A.length, s = Arrays.stream(A).sum();
        for (int i = 1; i <= n / 2; ++i) if (s * i % n == 0 && find(A, s * i / n, i, 0)) return true;
        return false;
    }

    public boolean find(int[] A, int target, int k, int i) {
        if (k == 0) return target == 0;
        if (k + i > A.length) return false;
        return find(A, target - A[i], k - 1, i + 1) || find(A, target, k, i + 1);
    }

https://zxi.mytechroad.com/blog/searching/leetcode-805-split-array-with-same-average/

  bool splitArraySameAverage(vector<int>& A) {

    std::sort(A.begin(), A.end());

    sum = std::accumulate(A.begin(), A.end(), 0);

    n = A.size();

    return dfs(A, 1, 0, 0);

}

private:

  int sum;

  int n;

  bool dfs(const vector<int>& A, int c, int s, int cur) {

    if (c > A.size() / 2) return false;

    for (int i = s; i < A.size(); ++i) {

      cur += A[i];      

      if (cur * (n - c)  == (sum - cur) * c) return true;

      if (cur * (n - c)  > (sum - cur) * c) break;

      if (dfs(A, c + 1, i + 1, cur)) return true;

      cur -= A[i];

}

    return false;

}

X. https://blog.csdn.net/magicbean2/article/details/79831339
1）如果一个长度为n的数组可以被划分为A和B两个数组，我们假设A的长度小于B并且A的大小是k，那么：total_sum / n == A_sum / k == B_sum / (n - k)，其中1 <= k <= n / 2。那么可以知道：A_sum = total_sum * k / n。由于A_sum一定是个整数，所以我们可以推导出total_sum * k % n == 0，那就是说，对于特定的total_sum和n而言，符合条件的k不会太多。这样我们在第一步中就首先验证是否存在符合条件的k，如果不存在就可以提前返回false。

2）如果经过第一步的验证，发现确实有符合条件的k，那么我们在第二步中，就试图产生k个子元素的所有组合，并且计算他们的和。这里的思路就有点类似于背包问题了，我们的做法是：定义vector<vector<unordered_set<int>>> sums，其中sums[i][j]表示A[0, i]这个子数组中的任意j个元素的所有可能和。可以得到递推公式是：sums[i][j] = sums[i - 1][j] "join" (sums[i][j - 1] + A[i])，其中等式右边的第一项表示这j个元素中不包含A[i]，而第二项表示这j个元素包含A[i]。这样就可以采用动态规划的思路得到sums[n - 1][k]了（1 <= k <= n / 2）。

3）有了sums[n - 1][k]，我们就检查sums[n - 1][k]中是否包含(total_sum * k / n)。一旦发现符合条件的k，就返回true，否则就返回false。

在递推公式中我们发现，sums[i][j]仅仅和sums[i - 1][j]，sums[i][j - 1]有关，所以可以进一步将空间复杂度从O(n^2*M)降低到O(n*M)，其中M是n中的所有元素的组合数（可能高达O(2^n)）。时间复杂度为O(n^3*M)。

bool splitArraySameAverage(vector<int>& A) {
int n = A.size(), m = n / 2;
int totalSum = accumulate(A.begin(), A.end(), 0);
// early pruning
bool isPossible = false;
for (int i = 1; i <= m; ++i) {
if (totalSum * i % n == 0) {
isPossible = true;
break;
}
}
if (!isPossible) {
return false;
}
// DP like knapsack
vector<unordered_set<int>> sums(m + 1);
sums[0].insert(0);
for (int num: A) { // for each element in A, we try to add it to sums[i] by joining sums[i - 1]
for (int i = m; i >= 1; --i) {
for (const int t: sums[i - 1]) {
sums[i].insert(t + num);
}
}
}
for (int i = 1; i <= m; ++i) {
if (totalSum * i % n == 0 && sums[i].find(totalSum * i / n) != sums[i].end()) {
return true;
}
}
return false;
}

X.
http://www.cnblogs.com/grandyang/p/10285531.html

这道题给了我们一个数组A，问我们是否可以把数组分割成两个小数组，并且要求分成的这两个数组的平均值相同。之前我们有做过分成和相同的两个小数组 Split Array with Equal Sum，看了题目中的给的例子，你可能会有种错觉，觉得这两个问题是一样的，因为题目中分成的两个小数组的长度是一样的，那么平均值相同的话，和一定也是相同的。但其实是不对的，很简单的一个例子，比如数组 [2, 2, 2]，可以分成平均值相同的两个数组 [2, 2] 和 [2]，但是无法分成和相同的两个数组。我们现在唯一知道的就是这两个数组的平均值相等，这里有个隐含条件，就是整个数组的平均值也和这两个数组的平均值相等，这个不用多说了吧，加法的结合律的应用啊。由于平均值是由数字总和除以个数得来的，那么假设整个数组有n个数组，数字总和为sum，分成的其中一个数组有k个，假设其数字和为sum1，那么另一个数组就有n-k个，假设其数组和为sum2，那么我们就有如下等式：

sum / n = sum1 / k = sum2 / (n - k)

我们看前两个等式，sum / n = sum1 / k，可以变个形，sum * k / n = sum1，那么由于数字都是正数，所以 sum * k 一定可以整除 n，这个可能当作一个快速的判断条件。下面来考虑k的取值范围，由于要分成两个数组，我们可以始终将k当作其中较短的那个数组，则k的取值范围就是 [1, n/2]，就是说，如果在这个范围内的k，没有满足的 sum * k % n == 0 的话，那么可以直接返回false，这是一个快速的剪枝过程。如果有的话，我们也不能立即说可以分成满足题意的两个小数组，最简单的例子，比如数组 [1, 3]，当k=1时，sum * k % n == 0 成立，但明显不能分成两个平均值相等的数组。所以还需要进一步检测，当我们找到满足的 sum * k % n == 0 的k了时候，我们其实可以直接算出 sum1，通过 sum * k / n，那么我们就知道较短的数组的数字之和，只要我们能在原数组中数组找到任意k个数字，使其和为sum1，那么就可以split成功了。问题到这里就转化为了如何在数组中找到任意k个数字，使其和为一个给定值。有点像 Combination Sum III 那道题，我们当然可以根据不同的k值，都分别找原数组中找一遍，但我们想更高效一点，因为毕竟k的范围是固定的，我们可以事先任意选数组中k个数字，将其所有可能出现的数字和保存下来，最后再查找。那么为了去重复跟快速查找，我们可以使用HashSet来保存数字和，我们可以建立 n/2 + 1 个HashSet，多加1是为了不做数组下标的转换，并且防止越界，因为我们在累加的过程中，计算k的时候，需要用到k-1的情况。讲到这里，你会不会一拍大腿，吼道，这尼玛不就是动态规划Dynamic Programming么。恭喜你骚年，没错，这里我们的dp数组就是一个包含HashSet的数组，其中 dp[i] 表示数组中任选 i 个数字，所有可能的数字和。我们首先在 dp[0] 中加入一个0，这个是为了防止越界。我们更新 dp[i] 的思路是，对于dp[i-1] 中的每个数字，都加上一个新的数字，所以最外层的for循环是遍历原数组的中的每个数字的，中间的for循环是遍历k的，从n/2遍历到1，然后最内层的for循环是遍历dp[i-1]中的所有数组，加上最外层遍历到的数字，并存入dp[i]即可。整个dp数组更新好了之后，下面就是验证的环节了，对于每个k值，验证若 sum * k / n == 0 成立，并且 sum * i / n 在dp[i]中存在，则返回true。最后都没有成立的话，返回false

    bool splitArraySameAverage(vector<int>& A) {
        int n = A.size(), m = n / 2, sum = accumulate(A.begin(), A.end(), 0);
        bool possible = false;
        for (int i = 1; i <= m && !possible; ++i) {
            if (sum * i % n == 0) possible = true;
        }
        if (!possible) return false;
        vector<unordered_set<int>> dp(m + 1);
        dp[0].insert(0);
        for (int num : A) {
            for (int i = m; i >= 1; --i) {
                for (auto a : dp[i - 1]) {
                    dp[i].insert(a + num);
                }
            }
        }
        for (int i = 1; i <= m; ++i) {
            if (sum * i % n == 0 && dp[i].count(sum * i / n)) return true;
        }
        return false;
    }

下面这种解法跟上面的解法十分的相似，唯一的不同就是使用了bitset这个数据结构，在之前那道 Partition Equal Subset Sum 的解法二中，我们也使用了biset，了解了其使用方法后，就会发现使用这里使用它只是单纯的为了炫技而已。由于biset不能动态变换大小，所以初始化的时候就要确定，由于题目中限定了数组中最多30个数字，每个数字最大10000，那么就初始化n/2+1个biset，每个大小为300001即可。然后每个都初始化个1进去，之后更新的操作，就是把 bits[i-1] 左移 num个，然后或到 bits[i]即可，最后查找的时候，有点像二维数组的查找方式一样，直接两个中括号坐标定位即可，参见代码如下：

    bool splitArraySameAverage(vector<int>& A) {
        int n = A.size(), m = n / 2, sum = accumulate(A.begin(), A.end(), 0);
        bool possible = false;
        for (int i = 1; i <= m && !possible; ++i) {
            if (sum * i % n == 0) possible = true;
        }
        if (!possible) return false;
        bitset<300001> bits[m + 1] = {1};
        for (int num : A) {
            for (int i = m; i >= 1; --i) {
                bits[i] |= bits[i - 1] << num;
            }
        }
        for (int i = 1; i <= m; ++i) {
            if (sum * i % n == 0 && bits[i][sum * i / n]) return true;
        }
        return false;
    }

再来看一种递归的写法，说实话在博主看来，一般不使用记忆数组的递归解法，等同于暴力破解，基本很难通过OJ，除非你进行了大量的剪枝优化处理。这里就是这种情况，首先还是常规的k值快速扫描一遍，确保可能存在解。然后我们给数组排了序，然后对于满足 sum * k % n == 0 的k值，进行了递归函数的进一步检测。需要传入当前剩余数字和，剩余个数，以及在原数组中的遍历位置，如果当前数字剩余个数为0了，说明我们已经取完了k个数字了，那么如果剩余数字和为0了，则说明成功的找到了k个和为 sum * k / n 的数字，返回ture，否则false。然后看若当前要加入的数字大于当前的平均值，则直接返回false，因为我们已经给原数组排过序了，之后的数字只会越来越大，一旦超过了平均值，就不可能再降下来了，这是一个相当重要的剪枝，估计能过OJ全靠它。之后我们开始从start开始遍历，当前遍历的结束位置是原数组长度n减去当前剩余的数字，再加1，因为我们确保给curNum留够足够的位置来遍历。之后就是跳过重复，对于重复的数字，我们只检查一遍就好了。调用递归函数，此时的curSum要减去当前数字A[i]，curNum要减1，start为i+1，若递归函数返回true，则整个返回true。for循环退出后返回false。令博主感到惊讶的是，这个代码的运行速度比之前的DP解法还要快，叼，参见代码如下：

    bool splitArraySameAverage(vector<int>& A) {
        int n = A.size(), m = n / 2, sum = accumulate(A.begin(), A.end(), 0);
        bool possible = false;
        for (int i = 1; i <= m && !possible; ++i) {
            if (sum * i % n == 0) possible = true;
        }
        if (!possible) return false;
        sort(A.begin(), A.end());
        for (int i = 1; i <= m; ++i) {
            if (sum * i % n == 0 && helper(A, sum * i / n, i, 0)) return true;
        }
        return false;
    }
    bool helper(vector<int>& A, int curSum, int curNum, int start) {
        if (curNum == 0) return curSum == 0;
        if (A[start] > curSum / curNum) return false;
        for (int i = start; i < A.size() - curNum + 1; ++i) {
            if (i > start && A[i] == A[i - 1]) continue;
            if(helper(A, curSum - A[i], curNum - 1, i + 1)) return true;
        }
        return false;
    }

LeetCode 805 - Split Array With Same Average

Labels

Popular Posts