『LeetCode』2178 拆分成最多数目的正偶数之和

题目

给你一个整数 finalSum 。请你将它拆分成若干个 互不相同 的正偶数之和，且拆分出来的正偶数数目最多。

比方说，给你 finalSum = 12 ，那么这些拆分是 符合要求 的（互不相同的正偶数且和为 finalSum）：(2 + 10) ，(2 + 4 + 6) 和 (4 + 8) 。它们中，(2 + 4 + 6) 包含最多数目的整数。注意 finalSum 不能拆分成 (2 + 2 + 4 + 4) ，因为拆分出来的整数必须互不相同。

请你返回一个整数数组，表示将整数拆分成最多数目的正偶数数组。如果没有办法将 finalSum 进行拆分，请你返回一个空数组。你可以按任意顺序返回这些整数。

示例 1：

输入：finalSum = 12
输出：[2,4,6]
解释：以下是一些符合要求的拆分：(2 + 10), (2 + 4 + 6) 和 (4 + 8) 。
(2 + 4 + 6) 为最多数目的整数，数目为 3 ，所以我们返回 [2,4,6] 。
[2,6,4] ，[6,2,4] 等等也都是可行的解。

示例 2：

输入：finalSum = 7
输出：[]
解释：没有办法将 finalSum 进行拆分。
所以返回空数组。

示例 3：

输入：finalSum = 28
输出：[6,8,2,12]
解释：以下是一些符合要求的拆分：(2 + 26), (6 + 8 + 2 + 12) 和 (4 + 24) 。
(6 + 8 + 2 + 12) 有最多数目的整数，数目为 4 ，所以我们返回 [6,8,2,12] 。
[10,2,4,12] ，[6,2,4,16] 等等也都是可行的解。

提示：

1 <= finalSum <= 10^{10}

题解

【拆分成最多数目的正偶数之和】回溯&贪心及其证明

回溯

显然，奇数是不能拆分成正偶数之和的，所以对于奇数直接返回空数组即可。

对于偶数，从小到大枚举即可，尽可能先用小的数字再用大的数字

// Code language: C++
class Solution {
public:
    vector<long long> maximumEvenSplit(long long finalSum) {
        vector<long long> ans;
        if ((finalSum & 1) == 1) return ans;
        function<bool(long long, long long)> dfs = [&](long long cur, long long target) {
            if (target == 0) return true;
            else if (cur == target) {
                ans.emplace_back(cur);
                return true;
            }
            else {
                for (long long i = cur; i <= target; i += 2) {
                    ans.emplace_back(i);
                    if (dfs(i + 2, target - i)) return true;
                    ans.pop_back();
                }
            }
            return false;
        };
        for (long long i = 2; i <= finalSum; i += 2) {
            if (dfs(i, finalSum)) break;
        }
        return ans;
    }
};

时间复杂度: O(n), 由下面贪心的证明过程不难证明递归深度为 $O(\sqrt{n})$, 总的时间复杂度为 $O(\sqrt{n} \times \sqrt{n})$ 即 O(n), 但由于有剪枝，实际上远远小于 O(n)（不然也通过不了）
空间复杂度: O(log n)

贪心

最简单的办法就是优先取小的数字，取到不能取以后将余数加到最后一项。不难证明这样的贪心策略可以保证最多数目。

证明：

假设有 finalSum = 2 + 4 + … + 2n + x 其中 x 是按照贪心策略取到的余数，有 x < 2n，该策略取到的最多数目为 n 个。

考虑另一种策略，能取得 > n 的正偶数，即 finalSum = a₁ + a₂ + … + a_m, m > n，其中 a_i 是按照该策略取到的正偶数，且 a_i < a_i + 1 恒成立（即单调增），由于每个数字只能取一次，那么必然有 a_i > = 2i(注：2i 即贪心策略取得的第 i 项)，考虑 m = = n + 1, 则两种策略的最后几项为 2(n − 1), 2n + x 和 2a_n − 1, 2a_n, 2a_n + 1，由于 2a_n > = 2n, x < 2n 且 2a_n + 1 > 2a_n，则有 2n + x < 2a_n + 2a_n + 1

即有 finalSum > finalSum, 显然矛盾，故可取得最多数目为 n 个。

# Code language: Python
class Solution:
    def maximumEvenSplit(self, finalSum: int) -> List[int]:
        if finalSum & 1:
            return list()
        ans = list()
        for i in count(2, 2):
            if i > finalSum:
                break
            ans.append(i)
            finalSum -= i
        if finalSum:
            ans[-1] += finalSum
        return ans

// Code language: Java
class Solution {
    public List<Long> maximumEvenSplit(long finalSum) {
        List<Long> ans = new ArrayList<Long>();
        if ((finalSum & 1) == 1) return ans;
        for (long i = 2; i <= finalSum; i += 2) {
            ans.add(i);
            finalSum -= i;
        }
        if (finalSum > 0) ans.set(ans.size() - 1, ans.get(ans.size() - 1) + finalSum);
        return ans;
    }
}

// Code language: C++
class Solution {
public:
    vector<long long> maximumEvenSplit(long long finalSum) {
        vector<long long> ans;
        if ((finalSum & 1) == 1) return ans;
        for (long long i = 2; i <= finalSum; i += 2) {
            ans.emplace_back(i);
            finalSum -= i;
        }
        if (finalSum > 0) ans[ans.size() - 1] += finalSum;
        return ans;
    }
};

时间复杂度: $O(\sqrt{n})$，从证明中不难发现答案中最多只有 $\lceil \sqrt{n} \rceil$ 个数字
空间复杂度: O(1), 不考虑返回值

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』2178 拆分成最多数目的正偶数之和

题目

标签

题解

回溯

贪心