题解 | #数组分组#

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)