输入int型数组，询问该数组能否分成两组，使得两组中各元素加起来的和相等，并且，所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），不是5的倍数也不是3的倍数能放在任意一组，可以将数组分为空数组，能满足以上条件，输出true；不满足时输出false。
数据范围：每个数组大小满足 
，输入的数据大小满足 
[编程题]数组分组
这道题用递归真是精彩，参考排在前几楼的大神的。
之前都不知道return 可以对 | | 这个运算符有效
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<strstream>
using namespace std;
bool f(int sum1,int sum2,int *p,int len,int i)
{
if(i==len&&sum1==sum2)
return true;
if(i==len&&sum1!=sum2)
return false;
if(i<len)
{
return f(sum1+(*(p+i)),sum2,p,len,i+1)||f(sum1,sum2+(*(p+i)),p,len,i+1);
}
}
int main()
{
int n;
while(cin>>n)
{
int b[10000]= {0};
int a[10000]= {0};
int sum1=0,sum2=0;
int p=0;
for(int i=0; i<n; i++)
{
cin>>b[i];
if(b[i]%5==0)
sum1+=b[i];
else if(b[i]%3==0)
sum1+=b[i];
else
{
a[p++]=b[i];
}
}
int len=p;
int i=0;
bool iscan=f(sum1,sum2,a,len,0);
if(iscan)
cout<<"true"<<endl;
else
cout<<"false"<<endl;
}
return 0;
}
发表于 2019-10-12 18:04:58
回复(1)
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
//分三组， 第三组所有和的可能(类似砝码称重)
int main()
{
int n,val;
while(cin>>n){
vector<int> oth;
int sum5=0, sum3=0, sumoth=0;
//输入数据
while(n--) {
cin>>val;
if(val%5==0)
sum5 += val; //第一组的和
else if(val%3==0)
sum3 += val; //第二组的和
else {
oth.push_back(val); //第三组的值
sumoth += val; //第三组的和
}
}
//计算第三组和有多少种可能
set<int> wc,cp;
wc.insert(0);
for(auto iv:oth) {
cp = wc;
for(auto is:cp)
wc.insert(is+iv);
}
//判断条件是否满足
int flg=0;
for(auto is:wc)
if(is+sum5==sum3+sumoth-is)
flg=1;
cout<<(flg?"true":"false")<<endl;
}
}
发表于 2019-08-10 18:57:54
回复(0)
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
//若可能的话，将问题转化成，利用剩下的数据进行加减运算，得到一个数，
//这个数的绝对值和sum5-sum3的绝对值相同即为true。
// 我利用+-操作符的全排列做的
int main()
{
int n;
while(cin >> n)
{
int sum5 = 0;
int sum3 = 0;;
vector<int> ivec;
int temp;
for(int i = 0; i < n; i++)
{
cin >> temp;
if(temp % 5 == 0)
sum5 += temp;
else if(temp % 3 == 0)
sum3 += temp;
else
ivec.push_back(temp);
}
int t = ivec.size();
int sub = abs(sum5 - sum3);
bool flag = 0;
if( t == 0)
{
if(sum5 == sum3)
cout << "true" << endl;
else
cout << "false" << endl;
}
else
{
string s = "";
for(int i = 0; i < t-1; i++)
s += "+-";
sort(s.begin(),s.end());
do
{
int res = ivec[0];
for(int i = 1; i < t; i++)
{
if(s[i-1] == '+')
res += ivec[i];
else
res -= ivec[i];
}
if(abs(res) == sub)
{
cout << "true" << endl;
flag = 1;
break;
}
}while(next_permutation(s.begin(),s.end()));// 产生下一个全排列
}
if(!flag)
cout << "false" << endl;
}
}
发表于 2017-07-26 10:21:35
回复(4)
居然没有看到有用python通过这道题的，，，话说，本地编译应该没问题，牛客这就是错（所以没看到有python的童鞋通过吧
实质确实是背包问题-子集和为给定值，采用的方法直接暴力出所有子集，求各子集和，然后看是否有给定值，好吧，话说牛客也没提示我超市出错啊
import itertools
v1=int(raw_input())
v2=raw_input().split(' ')
v2=map(int,v2)
a=[]
b=[]
c=[]
for i in v2:
if i%5==0:
a.append(i)
elif i%3==0 and i%5!=0:
b.append(i)
else:
c.append(i)
a1=sum(a)
b1=sum(b)
c1=sum(c)
dif=abs(a1-b1)
#x-y=dif
#x+y=c1
x=(dif+c1)%2
y=(c1-dif)%2
if x==0 and y==0:###如果x,y均为0，也就是x1有整数解，才有可能找到满足结果的数组，接下来就是判断，在a中或者b中，能否找到子数组和恰好为x1
x1=(dif+c1)/2
tmp=[]
for i in range(1,len(c)+1):
tmp.extend(list(itertools.combinations(c,i)))
lst1=map(list,tmp)
out1=map(sum,lst1)
if x1 in out1:
print 'true'
else:
print 'false'
else:
print 'false'
发表于 2017-05-06 00:36:52
回复(0)
#include<stdio.h>
int main()
{
int num;
while(scanf("%d",&num)!=EOF)
{
int a[100];
int i;
for(i=0;i<num;i++)
{
scanf("%d",&a[i]);
}
int sum1=0;
int sum2=0;
int sum=0;
for(i=0;i<num;i++)
{
if(a[i]>0&&a[i]%5==0)
sum1+=a[i];
else if(a[i]>0&&a[i]%3==0)
sum2+=a[i];
else
sum+=abs(a[i]);
}
if(sum>abs(sum1-sum2)&&(sum-abs(sum1-sum2))%2==0)
printf("true\n");
else
printf("false\n");
}
return 0;
}
发表于 2020-11-27 22:46:54
回复(1)
#include<iostream>
#include<vector>
using namespace std;
//判断nums[index....len]放入fivesum和threesum中能否有组合使fivesum==threesum
bool isExists(int fivesum, int threesum, int index, vector<int>nums){
if (index == nums.size()){
if (fivesum == threesum){
return true;
}
else{
return false;
}
}
return isExists(fivesum + nums[index], threesum, index + 1, nums) || isExists(fivesum, threesum + nums[index], index + 1, nums);
}
int main(){
int n;
while (cin >> n){
vector<int>nums;
int a;
int fivesum = 0;
int threesum = 0;
for (int i = 0; i < n; i++){
cin >> a;
if (a % 5 == 0){//5的倍数放入fivesum
fivesum += a;
}
else if (a % 3 == 0){//3的倍数放入threesum
threesum += a;
}
else{//其他数放入nums中待分配
nums.push_back(a);
}
}
if (isExists(fivesum, threesum, 0, nums)){
cout << "true" << endl;
}
else{
cout << "false" << endl;
}
}
return 0;
}
发表于 2019-07-21 19:23:43
回复(2)
import java.util.Scanner;
//思想：将能整除3或者5的各自分为一组，记为sum1和sum2，剩余的保存在数组nums里
//现有两组，剩余nums里的数相加或减的值result 等于 abs(sum1 - sum2)即可
//最终nums里的数字全部组合，若 result == abs(sum1 - sum2)，则返回true，否则，返回false
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
int n = Integer.parseInt(scanner.nextLine());
int[] arr = new int[n];
String[] s = scanner.nextLine().split("\\s");
for(int i=0;i<n;i++){
arr[i] = Integer.parseInt(s[i]);
}
System.out.println(depart(arr,n));
}
}
private static boolean depart(int[] arr,int n) {
int[] nums = new int[n]; // 存不能能整除3或者5
int count = 0;
int sum1 = 0,sum2 = 0;
for(int i=0;i<n;i++){
if(arr[i] % 3 == 0){
sum1 += arr[i]; // 能能整除3的数之和
}else if(arr[i] % 5 == 0){
sum2 += arr[i]; // 存不整除5的数之和
}else{
nums[count++] = arr[i];
}
}
int sum = Math.abs(sum1 - sum2);
int i = 0;
int result = 0; //不能能整除3或者5 的组合值
return f(i,count,nums,sum,result);
}
private static boolean f(int i, int count, int[] nums, int sum,int result) {
if(i == count){
return result == sum;
}else{
int result1 = result + nums[i];
int result2 = result - nums[i];
i=i+1;
return (f(i,count,nums,sum,result1) || f(i,count,nums,sum,result2));
}
}
}
发表于 2018-05-17 11:30:26
回复(0)
Rust 题解，一个坑：不能用原数组的引用，必须用克隆。
fn main() {
let mut n = String::new();
let mut nums = String::new();
std::io::stdin().read_line(&mut n);
std::io::stdin().read_line(&mut nums);
let mut sum3 = 0;
let mut sum5 = 0;
let mut others = vec![];
nums.trim()
.split(" ")
.map(|n| n.parse::<i32>().unwrap())
.for_each(|n| {
if n % 5 == 0 {
sum5 += n;
} else if n % 3 == 0 {
sum3 += n;
} else {
others.push(n);
}
});
println!("{}", backtrack(others, sum3, sum5));
}
fn backtrack(mut nums: Vec<i32>, sum1: i32, sum2: i32) -> bool {
match nums.pop() {
Some(x) => {
backtrack(nums.clone(), sum1 + x, sum2) || backtrack(nums.clone(), sum1, sum2 + x)
}
None => sum1 == sum2,
}
}
发表于 2022-08-22 23:33:31
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<Integer> a = new ArrayList<>(n);
List<Integer> b = new ArrayList<>(n);
List<Integer> c = new ArrayList<>(n);
long sa = 0l;
long sum = 0l;
for (int i = 0; i < n; i++) {
int j = sc.nextInt();
if (j % 5 == 0) {
a.add(j);
sa += j;
} else if (j % 3 == 0) {
b.add(j);
sum += j;
} else {
c.add(j);
sum += j;
}
}
sum += sa;
if (Math.abs(sum % 2) == 1) {
System.out.println(false);
return;
}
long d = sum / 2 - sa;
if (dfs(c, d, 0)) {
System.out.println(true);
} else {
System.out.println(false);
}
}
static boolean dfs(List<Integer> a, long m, int i) {
if (i == a.size()) {
return m == 0;
}
if (dfs(a, m, i + 1)) {
return true;
}
if (dfs(a, m - a.get(i), i + 1)) {
return true;
}
return false;
}
}
发表于 2022-07-06 01:00:47
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
List<Integer> group_3 = new ArrayList<>();
List<Integer> group_5 = new ArrayList<>();
List<Integer> group_free = new ArrayList<>();
int count = sc.nextInt();
while (count > 0) {
int num = sc.nextInt();
if (num % 5 == 0) {
group_5.add(num);
} else if (num % 3 == 0) {
group_3.add(num);
} else {
group_free.add(num);
}
count--;
}
int sum_3 = 0, sum_5=0;
for (int i : group_3) {
sum_3 += i;
}
for (int i : group_5) {
sum_5 += i;
}
System.out.println(process(group_free, 0, sum_3, sum_5));;
}
private static boolean process(List<Integer> free, int index, int sum_3, int sum_5) {
if (index == free.size()) {
if (sum_3 == sum_5) {
return true;
} else {
return false;
}
}
boolean giveTo3 = process(free, index + 1, sum_3 + free.get(index), sum_5);
boolean giveTo5 = process(free, index + 1, sum_3, sum_5 + free.get(index));
return giveTo3 || giveTo5;
}
}
发表于 2022-06-06 23:48:48
回复(0)
//常规递归思路
import java.util.*;
public class Main {
//flag可进行后续减枝操作
public static boolean flag;
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
flag = false;
recur(nums, 0, 0, 0);
System.out.println(flag);
}
}
public static void recur(int[] nums, int idx, int sum5, int sum3) {
if (idx == nums.length) {
if (sum5 == sum3) {
flag = true;
}
return;
}
if (nums[idx] % 5 == 0) {
recur(nums, idx + 1, sum5 + nums[idx], sum3);
} else if (nums[idx] % 3 == 0 && nums[idx] % 5 != 0) {
recur(nums, idx + 1, sum5, sum3 + nums[idx]);
} else {
recur(nums, idx + 1, sum5 + nums[idx], sum3);
recur(nums, idx + 1, sum5, sum3 + nums[idx]);
}
}
}
发表于 2022-03-02 10:52:43
回复(0)
记数组的和为sum，显然只有sum为偶数时才有可能分解成两个和相等的子数组。先将5的倍数进行求和为sum1，3的倍数且非5的倍数求和为sum2，然后判断剩下的数能否凑出sum1就可以了(子集和问题)。
然后用递归来求解子集和问题，每层递归只考虑是否选择头部的元素进行求和，然后对当前数组切片nums[1:]进行下一层递归，只要这两种方式中有一种能够凑出指定和就行。
def judge(nums, target):
n = len(nums)
if n == 1 and nums[0] == target:
return True
elif n > 1:
# 选择第一个数和不选第一个数两种情况
return judge(nums[1:], target - nums[0])&nbs***bsp;judge(nums[1:], target)
return False
while True:
try:
n = int(input())
arr = list(map(int, input().strip().split()))
total = sum(arr)
if total % 2 == 1:
print("false")
else:
target = total // 2 # 两组数的目标和
group3, group5, other = 0, 0, []
for num in arr:
if num % 5 == 0:
group5 += num # 5的倍数进行求和
elif num % 3 == 0 and num % 5 != 0:
group3 += num # 不包括5的倍数的3的倍数进行求和
else:
other.append(num)
# 检查other中的数能不能凑出和为target-group3以及和为target-group5的两部分
print("true" if judge(other, target - group3) else "false")
except:
break
编辑于 2021-04-02 15:52:28
回复(0)
牛客网的判卷系统真的有病，本地可以执行，自测可以执行。但是就是print('true')输出不了，在print('true')语句前后加上print('123')都可以输出，就是这句话输出不了，这道题真是日了牛客网了
def findm(n, m):
if m < 1&nbs***bsp;len(n) < 1:
return
elif m in n:
return True
if findm(n[:-1], m):
return True
elif findm(n[:-1], m - n[-1]):
return True
else:
return False
def pf(f):
if f:
print('true')
else:
print('false')
try:
n = int(input())
m = list(map(int, input().split()))
li3 = []
li5 = []
res = []
for i in range(len(m)):
if m[i] % 5 == 0:
li5.append(m[i])
elif m[i] % 3 == 0:
li3.append(m[i])
else:
res.append(m[i])
sumall = sum(m)
if sumall % 2:
print('false')
else:
M = int(sumall / 2 - sum(li5))
pf(findm(res,M))
#if findm(res, M):
except Exception as e:
print(e)
发表于 2020-09-03 17:07:20
回复(1)
#include "stdio.h"
#include "math.h"
#include <stdbool.h>
bool func(int i, int a[], int n, int ret, int sum)
{
if(i == n)
return abs(ret) == abs(sum);
return func(i+1, a, n, ret+a[i], sum) || func(i+1, a, n, ret-a[i], sum);
}
int main()
{
int n;
while(scanf("%d", &n) != EOF) {
int i, j = 0, a[n], sum3=0, sum5=0, other[n];
for(i=0; i<n; i++) {
scanf("%d", &a[i]);
if(a[i]%3 == 0) {
sum3 += a[i];
} else if(a[i]%5 == 0) {
sum5 += a[i];
} else
other[j++] = a[i];
}
int sum = abs(sum3-sum5);
if(func(0, other, j, 0, sum) == true)
puts("true");
else
puts("false");
}
}
编辑于 2020-07-05 16:08:01
回复(0)
import java.util.*;
public class Main{
public static void main(String []args){
int sum=0;
int sum3=0;
int sum5=0;
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
ArrayList<Integer> arr=new ArrayList();
while(sc.hasNext()){
int a=sc.nextInt();
if(Math.abs(a)%5==0){
sum5+=a;
continue;
}else if(Math.abs(a)%3==0){
sum3+=a;
continue;
}
sum+=a;
}
if(Math.abs((Math.abs(sum)-(Math.max(sum3,sum5)-Math.min(sum3,sum5))))%2==0){
System.out.println("true");
}else{
System.out.println("false");
}
}
} 
然后同样的测试用例在提交就是不通过？？？？为啥。。。
发表于 2020-06-17 15:13:22
回复(4)
#include <iostream>
#include <vector>
using namespace std;
bool istrue(int sum1, int sum2, vector<int> list, int index)
{
if(index==list.size() && sum1!=sum2) return false;
if(index==list.size() && sum1==sum2) return true;
if(index!=list.size())
return(istrue(sum1+list[index], sum2, list, index+1) || istrue(sum1, sum2+list[index], list, index+1) );
}
int main()
{
int num;
while(cin>>num)
{
vector<int> list;
int sum1=0,sum2=0;
for(int i=0;i<num;i++){
int tmp;
cin>>tmp;
if(tmp%5==0)
sum1+=tmp;
else if(tmp%3==0)
sum2+=tmp;
else
list.push_back(tmp);
}
bool flag = istrue(sum1,sum2,list,0);
if(flag==1) cout<<"true"<<endl;
else cout<<"false"<<endl;
}
}
#include <vector>
using namespace std;
bool istrue(int sum1, int sum2, vector<int> list, int index)
{
if(index==list.size() && sum1!=sum2) return false;
if(index==list.size() && sum1==sum2) return true;
if(index!=list.size())
return(istrue(sum1+list[index], sum2, list, index+1) || istrue(sum1, sum2+list[index], list, index+1) );
}
int main()
{
int num;
while(cin>>num)
{
vector<int> list;
int sum1=0,sum2=0;
for(int i=0;i<num;i++){
int tmp;
cin>>tmp;
if(tmp%5==0)
sum1+=tmp;
else if(tmp%3==0)
sum2+=tmp;
else
list.push_back(tmp);
}
bool flag = istrue(sum1,sum2,list,0);
if(flag==1) cout<<"true"<<endl;
else cout<<"false"<<endl;
}
}
发表于 2020-06-16 12:47:09
回复(0)
#~万物皆可递归~
#include <stdbool.h>
bool s;
void checkGetin(int num[],int numt[],int numf[],int m,int k,int kt,int kf){
if (m==k) {
int count1=0,count2=0;
for (int i=0; i<kt; i++)
count1+=numt[i];
for (int i=0; i<kf; i++)
count2+=numf[i];
if (count1==count2)
s=true;
return;
}
numt[kt++]=num[m++];
checkGetin(num, numt, numf, m, k, kt, kf);
kt--; m--;
numf[kf++]=num[m++];
checkGetin(num, numt, numf, m, k, kt, kf);
}
int main(){
void checkGetin(int [],int [],int [],int ,int ,int ,int );
int n;
while (~scanf("%d",&n)) {
int num[1000],numt[500],numf[500];
int k=0,kt=0,kf=0;
for (int i=0; i<n; i++) {
int temp;
scanf("%d",&temp);
if (temp%3==0)
numt[kt++]=temp;
else if (temp%5==0)
numf[kf++]=temp;
else
num[k++]=temp;
}
s=false;
checkGetin(num, numt, numf, 0, k, kt, kf);
if (s)
printf("true\n");
else
printf("false\n");
}
return 0;;
}
发表于 2020-05-26 11:17:19
回复(0)
就只有我一个人觉得题目和测试用例给的有问题吗，题目说了将两组中各元素加起来的和相等，就是最简单的加法运算，和减法，取绝对值有什么关系，1，5，-5，1.怎么分配才能让分成的两组数组加起来和一样呢
发表于 2020-03-20 08:39:51
回复(0)
问题信息
难度：
292条回答
1780收藏
40085浏览
通过挑战的用户
查看代码-
2022-09-16 11:42:25 -
2022-09-16 10:19:55 -
2022-09-16 09:40:07 -
2022-09-15 23:57:39
-
2022-09-15 23:44:03
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
