DFS with Optimization in Golang


  • 0
    S
    import (
        "fmt"
        "sort"
    )
    
    func makesquare(nums []int) bool {
        sort.Sort(sort.Reverse(sort.IntSlice(nums)))
        sum := 0
        for _, num := range nums {
            sum += num
        }
        if sum % 4 != 0 || sum == 0 {
            return false
        }
        
        square := make([]int, 4)
        return makeHelper(square, nums, 0, sum/4)
    }
    
    func makeHelper(square []int, nums []int, index int, target int) bool {
        if index == len(nums){
            res := square[0] == target && square[0] == square[1] && square[1] == square[2] && square[2] == square[3]
            return res
        }
        for pos, _ := range square {
            if square[pos] + nums[index] > target {
                continue
            }
            square[pos] += nums[index] 
            if makeHelper(square, nums, index+1, target) {
                return true
            }
            square[pos] -= nums[index]
        }
        return false
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.