[LeetCode] 306. Additive Number

😎풀이

1. backTracking 함수를 정의한다.
   1-1. index는 검사할 항목(num1 + num2)의 시작 인덱스를 정의
   1-2. count는 현재까지 조합된 수의 수를 의미 (최소 세 가지의 수가 있어야 Additive Number)
   1-3. num1과 num2의 합을 문자화 하여 검사 대상이 이들의 합과 같다면 재귀적으로 문자 끝까지 검사하며 세가지 이상의 수로 이루어진 경우 true 아닐 경우 false 반환
2. 2중 순회
   2-1. 단, i가 전체 길이의 절반을 넘길 경우 자릿수 때문에 어떠한 합으로도 Additive Number가 될 수 없으므로 절반까지만 순회
   2-2. 각 자리를 잘라 2자리 이상이라면 0으로 시작하는 수가 아닐 경우 백트레킹
3. 생성 가능 여부 반환

function isAdditiveNumber(num: string): boolean {
    const n = num.length
    function backTracking(index: number, num1: bigint, num2: bigint, count: number) {
        if(index === n) return count >= 3
        const sum = num1 + num2
        const sumStr = sum.toString()
        if(num.startsWith(sumStr, index)) return backTracking(index + sumStr.length, num2, sum, count + 1)
        return false
    }
    for(let i = 1; i <= Math.floor(n / 2); i++) {
        for(let j = i + 1; j < n; j++) {
            const num1 = num.slice(0, i)
            const num2 = num.slice(i, j)
            if(num1.length > 1 && num1[0] === '0') continue
            if(num2.length > 1 && num2[0] === '0') continue
            if(backTracking(j, BigInt(num1), BigInt(num2), 2)) return true
        }
    }
    return false
};