输入int型数组,询问该数组能否分成两组,使得两组中各元素加起来的和相等,并且,所有5的倍数必须在其中一个组中,所有3的倍数在另一个组中(不包括5的倍数),不是5的倍数也不是3的倍数能放在任意一组,可以将数组分为空数组,能满足以上条件,输出true;不满足时输出false。
数据范围:每个数组大小满足 ,输入的数据大小满足
第一行是数据个数,第二行是输入的数据
返回true或者false
4 1 5 -5 1
true
第一组:5 -5 1 第二组:1
3 3 5 8
false
由于3和5不能放在同一组,所以不存在一种分法。
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, } }
use std::io; fn is_str_numeric(s: &str) -> Option<i32> { for c in s.to_string().chars() { if !c.is_digit(10) && c != '-' { return None; } } Some(s.parse().unwrap()) } fn have_same_sum(nums_five: &[i32], nums_three: &[i32], nums_others: &[i32]) -> bool { if nums_others.is_empty() { return nums_five.iter().sum::<i32>() == nums_three.iter().sum::<i32>(); } return have_same_sum(&[nums_five, &[nums_others[0]]].concat(), nums_three, &nums_others[1..]) || have_same_sum(nums_five, &[nums_three, &[nums_others[0]]].concat(), &nums_others[1..]); } fn main() { let stdin = io::stdin(); let mut n = String::new(); while let Ok(len) = stdin.read_line(&mut n) { if len <= 0 { break; } let mut line = String::new(); stdin.read_line(&mut line).unwrap(); line.truncate(line.len() - 1); let nums: Vec<i32> = line .split(" ") .filter_map(|c| is_str_numeric(c)) .collect(); let nums_five: Vec<i32> = nums .iter() .filter(|&num| num % 5 == 0) .cloned() .collect(); let nums_three: Vec<i32> = nums .iter() .filter(|&num| num % 3 == 0) .cloned() .collect(); let nums_others: Vec<i32> = nums .iter() .filter(|&num| num % 3 != 0 && num % 5 != 0) .cloned() .collect(); println!("{}", have_same_sum(nums_five.as_slice(), nums_three.as_slice(), nums_others.as_slice())); } }