题解 | #数组分组#
数组分组
https://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86
#include <bits/stdc++.h> using namespace std; bool dp(vector<int> &nums, int t, int k){ if(t == 0 && k == nums.size()) return true; if(k == nums.size()) return false; //如果只是3的倍数,不能加到该集合中。 if(nums[k] % 3 == 0) return dp(nums, t, k + 1); if(nums[k] == t) return true; //对于一个数有两种选择,加或者不加到该集合中 return dp(nums, t - nums[k], k + 1) || dp(nums, t, k + 1); // } int main(){ int n = 0; while(cin >> n){ /*//法一 vector<int> nums; int sum = 0; //只要找到总和的一半即可,剩下的数字之和自然为总和的一半。 int part = 0; //5的倍数的数字之和 for(int i =0; i < n; i++){ int num = 0; cin >> num; if(num % 5 == 0) part += num; //如果是5的倍数,不放入数组nums else nums.push_back(num); sum += num; } //如果所有数之和不是偶数,则肯定是false if (sum%2){ cout<<"false"<<endl; } else{ sum = sum / 2; if(dp(nums, sum - part, 0)){ cout << "true" << endl; } else cout<<"false"<<endl; } nums.clear();*/ //法二 vector<int> arr; int sum3 = 0; int sum5 = 0; int rest = 0; //剩余的数的和 for(int i = 0; i < n; i++){ int x; cin >> x; if(x % 5 == 0) //先求一个组的和 sum5 += x; else if(x % 3 == 0) //再求另一个组的和 sum3 += x; else{ arr.push_back(x); //剩余的加入数组并求和 rest += x; } } // unordered_set<int> s1, s2; s1.insert(0); //枚举所有组合的不重复和,0代表空数组 for(int i = 0; i < arr.size(); i++){ //遍历剩余的每一个数字,枚举所有可能性 s2 = s1; // for(auto iter : s2){ s1.insert(iter + arr[i]); //s1中保存的是所有的剩余数的和的可能性 } } bool res = false; for(auto iter : s1){ //遍历枚举的集合 if(iter + sum5 == sum3 + (rest - iter)){ //分成两部分后相等 res = true; break; } } cout << (res ? "true" : "false") << endl; } return 0; }
华为题库题解 文章被收录于专栏
牛客华为题库的题解