huawei od机试 等和子数组最小和_华为od 等和子数组最小和

698. 划分为k个相等的子集 - 力扣（LeetCode）   和这道题基本是相同的，就是多了一个循环，从大到小除，就可以找到最小和

leetcode 698. 划分为k个相等的子集-CSDN博客

//huafenzuixiaoxiangdengziji.cpp
//https://zhuanlan.zhihu.com/p/643824546
//https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solutions/2479339/698-hua-fen-wei-kge-xiang-deng-de-zi-ji-hd44o/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool compare(int &a, int &c) {
    return a > c;
}
bool recursion(int sum, vector<int>& nums, int start, int len, int target, vector<bool>& status, int k) {
    if(k==1) return true; //最后还剩下一个数组需要找，但是默认不需要找了 allsum - (k-1)*target = target，直接返回的呢
    if(sum==target) return recursion(0, nums, 0, len, target, status, k-1); // 满足条件的，找到了一个子数组，剩下要找的子数组数量减一：k-1
    int tmpsum=0;
    // 不在循环内做判断，判断交给了上面的sum==target，循环内只做剪枝和加和
    // 循环内只累加一个数字，剩下可能的累加交给了其他递归
    for(int i = start; i < len; i++) {             // 每个递归的循环都只处理一个 数字的加和，剩下的交给其他递归处理
        if(status[i]==true) continue; // 剪枝，这个数字已经标记true，累加过了的
        tmpsum = sum + nums[i]; //累加
        if(tmpsum > target) {   // 剪枝，累加和>target，可以直接跳过
            continue;
        }
        status[i] = true; //和这个数字相加，状态置true
        if(recursion(tmpsum, nums, i+1, len, target, status, k)) return true;   // 交给其他递归处理，和剩下的数字相加，起始点 i+1
        // 返回了false，也就是不满足条件，不能和这个数字相加，回溯的false
        status[i] = false;
        while(i+1 < len && nums[i+1]==nums[i]) { // 既然不能和这个数字相加，那么剩下的相等的数字就可以直接跳过，剪枝
            i++;     
        }
    }
    return false;  // 都尝试累加过了，剩下的数字没有符合条件的，返回false。
}
class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k, int target) {
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] > target) {
                return false;
            }
        }
        vector<bool> status(nums.size(), false);
        bool ret = recursion(0, nums, 0, nums.size(), target, status, k);
        return ret;
    }
};
 
int main(void) {
    int i, j, k, m, n, x, y, z, sum = 0;
    // k = 2*2;
    // int a[] = {4, 3, 2, 3, 5, 2, 1};
    // k = 3;
    // int a[] = {1, 2, 3, 4};
    int a[] = {4,3,2,3,5,2,1};
    int len = sizeof(a) / sizeof(*a);
    vector<int> arr(len);
    for(i = 0; i < len; i++) {
        arr[i] = a[i];
    }
    // for(i = 0; i < k; i++) scanf("%d", &arr[i]);
    sort(arr.begin(), arr.end(), compare);
    for(i = 0; i < arr.size(); i++) {
        sum += arr[i];
    }
    Solution ltt = Solution();
    bool ret;
    for(k = len; k >= 1; k--) {
        if(sum%k!=0) {
            continue;
        }
        ret = ltt.canPartitionKSubsets(arr, k, sum / k);
        if(ret) {
            cout<<sum / k<<endl;
            return 0;
        }
    }
    cout<<"false"<<endl;
    return 0;
}