等和子数组最小和

华为od机试真题

题目描述

给定一个数组nums，将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，组内元素和的最小值。

输入描述

第一行输入 m 接着输入m个数，表示此数组nums

数据范围：1 <= m <= 50, 1 <= nums[i] <= 50

输出描述

最小拆分数组和

示例1

输入：
7
4 3 2 3 5 2 1

输出：
5

说明：
可以等分的情况有：
4 个子集（5），（1,4），（2,3），（2,3）
2 个子集（5, 1, 4），（2,3, 2,3）
但最小的为5。

题解

题目类型

这是一个回溯问题，实际上属于经典的“子集划分”问题。要求将数组中的元素划分为若干个子集，使得每个子集的和相等。问题的难点在于如何高效地找出所有满足条件的分组，并从中选出组和的最小值。

解题思路

问题转化：我们要将数组划分成若干个子集，要求每个子集的和相等。我们需要首先计算所有元素的和 sum，然后尝试不同的子集和 x，使得每个子集的和为 x，并且能将所有元素恰好划分为多个子集。最小的 x 就是答案。

优化：

可以通过排序数组，将大元素先分配到子集，这样可以减少回溯的搜索次数。

通过回溯算法，枚举所有可能的子集和 x，对每一个 x，判断是否能够将数组划分为若干个和为 x 的子集。

关键函数：

canPartitionKSubsets：判断是否能将数组划分成 k 个和相等的子集。

backtrack：回溯法用于尝试将当前元素放入每一个子集，若某个子集的和超过了目标和，则回退。

时间复杂度与空间复杂度：

时间复杂度：在最坏情况下，回溯法会枚举所有子集，时间复杂度大约是 O(2^n)。

空间复杂度：主要是递归栈的空间和存储子集的空间，复杂度是 O(n)。

C++

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    // 能否将数组划分成 k 个相等的子集
    bool canPartitionKSubsets(vector<int> &nums, int k) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % k) return false;

        // 定义 k 个子集
        vector<int> groups(k, 0);
        return backtrack(nums, 0, groups, total / k);
    }

    bool backtrack(vector<int> &nums, int idx, vector<int> &groups, const int S) {
        // 完成划分
        if (idx == nums.size()) return true;
		
        // 遍历所有的 k 个组，尝试将 nums[idx] 放入一个组中
        for (int i = 0; i < groups.size(); i++) {
            // 当前组和超出目标和，跳过
            if (groups[i] + nums[idx] > S) continue;
            // 剪枝：当前组的和和前一个组的和相同，则跳过
            if (i > 0 && groups[i] == groups[i - 1]) continue;

            // 将 idx 个数字分配给第 i 个组中
            groups[i] += nums[idx];
            if (backtrack(nums, idx + 1, groups, S)) return true;
            groups[i] -= nums[idx]; // 回溯状态
        }

        return false;
    }
};

int main() {
    int m;
    cin >> m;
    vector<int> nums(m);
    for (int i = 0; i < m; i++) cin >> nums[i];

    // 降序排序，可以减少回溯搜索的次数
    sort(nums.begin(), nums.end(), greater<int>()); 

    int max = nums[0], sum = accumulate(nums.begin(), nums.end(), 0);
    int ans = sum;
    Solution s;

    // 子集和的可能范围 [max ~ sum]， 从小到大的方式进行枚举尝试
    for (int x = max; x < sum; x++) {
        if (sum % x) continue; // 除不尽，不可能组内元素和为 x

        if (s.canPartitionKSubsets(nums, sum / x)) {
            ans = x;
            break;
        }
    }

    cout << ans << endl;
    return 0;
}