Swift solution - DFS


  • 0
    class Solution {
        func makesquare(_ nums: [Int]) -> Bool {
            if nums.count < 4 {
                return false
            }
            
            var sum = 0
            for num in nums {
                sum += num
            }
            if sum % 4 != 0 {
                return false
            }
            
            let sortedNums = nums.sorted { $0 > $1 }
            var sums = [Int](repeatElement(0, count: 4))
            
            return DFS(sortedNums, &sums, 0, sum / 4)
        }
        
        private func DFS(_ nums: [Int], _ sums: inout [Int], _ pos: Int, _ target: Int) -> Bool {
            if pos == nums.count {
                if sums[0] == target && sums[1] == target && sums[2] == target {
                    return true
                }
                return false
            }
            
            for i in 0..<4 {
                if sums[i] + nums[pos] > target {
                    continue
                }
                sums[i] += nums[pos]
                if DFS(nums, &sums, pos + 1, target) {
                    return true
                }
                sums[i] -= nums[pos]
            }
            
            return false
        }
    }
    

Log in to reply
 

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