题解 | #数组分组#
数组分组
https://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86
package main import ( "fmt" "sort" ) func isValid(nums []int, pathIdxs []int) bool { var arr1 []int var arr2 []int idxMap := make(map[int]struct{}, 0) for _, idx := range pathIdxs { idxMap[idx] = struct{}{} } for i:=0; i<len(nums); i++ { if _, ok := idxMap[i]; !ok { arr1 = append(arr1, nums[i]) } else { arr2 = append(arr2, nums[i]) } } arr1HasThree, arr1HasFive := false, false arr2HasThree, arr2HasFive := false, false for _, num := range arr1 { if num == 0 { continue } if num % 3 == 0 { arr1HasThree = true } if num % 5 == 0 { arr1HasFive = true } } for _, num := range arr2 { if num == 0 { continue } if num % 3 == 0 { arr2HasThree = true } if num % 5 == 0 { arr2HasFive = true } } if arr1HasThree && arr1HasFive { return false } if arr2HasThree && arr2HasFive { return false } if arr1HasThree && arr2HasThree { return false } if arr1HasFive && arr2HasFive { return false } return true } func backtracking(nums []int, start int, sum int, path []int, target int) bool { if start > len(nums) { return false } if sum == target { // fmt.Printf("candidate: %+v\n", path) if isValid(nums, path) { return true } return false } // if sum > target { // return false // } for i:=start; i<len(nums); i++ { path = append(path, i) sum += nums[i] if backtracking(nums, i+1, sum, path, target) { return true } sum -= nums[i] path = path[:len(path)-1] } return false } func main() { var n int fmt.Scan(&n) var nums []int for i:=0; i<n; i++ { var num int fmt.Scan(&num) nums = append(nums, num) } sort.Ints(nums) var path []int var target int for _, num := range nums { target += num } if target % 2 != 0 { fmt.Println(false) } else { fmt.Println(backtracking(nums, 0, 0, path, target/2)) } }
// 本题输入为一行整数,所以采用:fmt.Scan(&n)