Leetcode 823 Solution

This article provides solution to leetcode question 823 (split-array-with-same-average)
Categories:
Tags:
Access this page by simply typing in "lcs 823" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution {
public:
    bool checkSum(vector<int>& A, int i, int target, int cnt) {
        if (target == 0 && cnt == 0)
            return true;
        else if (target <= 0 || cnt <= 0 || i == A.size())
            return false;

        for (int j = i; j < A.size(); j++)
        {
            if (j > i && A[j] == A[j - 1])
                continue;

            if (checkSum(A, j + 1, target - A[j], cnt - 1))
                return true;
        }

        return false;
    }

    bool splitArraySameAverage(vector<int>& A) {
        int n = A.size();
        int sum = 0;

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

        for (auto val: A)
            sum += val;

        for (int i = 1; i < n; i++)
        {
            if (sum * i % n)
                continue;

            if (checkSum(A, 0, sum * i / n, i))
                return true;
        }

        return false;
    }
};