[LeetCode] 698. Partition to K Equal Sum Subsets

😎풀이

1. nums의 총합을 k로 나눌 수 없다면 같은 값으로 N등분 불가
2. 백트레킹을 활용하여 재귀적 탐색
   2-1. 내림차 순 정렬된 숫자를 추가해보며 모든 숫자를 사용할 수 있는지 검증
3. 0번째 인덱스부터 백트레킹 수행 후 결과여부 반환

function canPartitionKSubsets(nums: number[], k: number): boolean {
    const total = nums.reduce((acc, cur) => acc + cur, 0)
    if(total % k !== 0) return false
    const target = total / k
    const descSorted = nums.toSorted((a, b) => b - a)
    const subsets = Array(k).fill(0)
    function backTrack(idx: number) {
        if(idx === nums.length) return true
        const num = descSorted[idx]
        for(let i = 0; i < k; i++) {
            if(subsets[i] + num <= target) {
                subsets[i] += num
                if(backTrack(idx + 1)) return true
                subsets[i] -= num
            }
            if (subsets[i] === 0) break;
        }
        return false
    }
    return backTrack(0)
};