[LeetCode] 473. Matchsticks to Square

😎풀이

1. 최소 성냥의 수가 4개 이상인지 검증
2. 길이의 총합이 4로 나누어 떨어져 정사각형을 이룰 수 있는지 검증
3. 내림차 순으로 정렬하여 가지치기 최적화
4. 백트레킹 활용
   4-1. 한 변의 최대 길이를 초과하지 않는 선에서 현재 변에 성냥 할당
   4-2. 모든 성냥이 할당되었을 때, 정사각형을 이뤘음을 확인

function makesquare(matchsticks: number[]): boolean {
    const n = matchsticks.length
    if(n < 4) return false
    const sum = matchsticks.reduce((acc, cur) => acc + cur, 0)
    if(sum % 4 !== 0) return false
    const sideLen = sum / 4
    const sorted = matchsticks.sort((a, b) => b - a)
    function backTrack(idx: number, sides: number[]) {
        if(idx === n) return sides.every(side => side === sides[0])
        for(let i = 0; i < sides.length; i++) {
            if(sides[i] + sorted[idx] > sideLen) continue
            sides[i] += sorted[idx]
            if(backTrack(idx + 1, [...sides])) return true
            sides[i] -= sorted[idx]
        }
        return false
    }
    return backTrack(0, [0, 0, 0, 0])
};