93. 유효 IP 주소 복원하기

문제는 주어진 숫자 문자열에서 올바른 IP 주소를 생성하는 것입니다. 유효한 IP는 다음과 같은 조건을 만족해야 합니다:

• 총 네 개의 정수로 구성되며 각각은 0~255 범위에 있어야 함
• 각 정수는 선행 0을 포함할 수 없음 (예: "01", "00")
• 정수 간에는 점(.)으로 구분됨

이 문제는 문자열을 분할하는 형태로 백트래킹 알고리즘을 적용하여 모든 가능한 조합을 탐색하는 방식으로 해결됩니다.

function restoreIpAddress(inputStr) {
    const results = [];
    const segments = [];
    
    function explore(index) {
        // 이미 4개 이상의 세그먼트가 있으면 종료
        if (segments.length > 4) return;
        
        // 정확히 4개 세그먼트이고 모든 문자를 사용했으면 결과 추가
        if (segments.length === 4 && index === inputStr.length) {
            results.push(segments.join('.'));
            return;
        }

        // 현재 위치부터 최대 3자리까지 시도
        for (let end = index; end < inputStr.length; end++) {
            const segment = inputStr.slice(index, end + 1);
            
            // 길이 초과 또는 값이 255 초과면 더 이상 진행 불필요
            if (segment.length > 3 || parseInt(segment) > 255) break;
            
            // 선행 0이 있는 경우 무시
            if (segment.length > 1 && segment[0] === '0') break;

            segments.push(segment);
            explore(end + 1);
            segments.pop();
        }
    }

    explore(0);
    return results;
}

78. 고유 요소로 구성된 부분집합 생성

배열의 모든 부분집합(멱집합)을 반환하는 문제입니다. 이때 중복된 부분집합은 허용되지 않으며 순서는 상관없습니다.

부분집합 문제는 트리의 모든 노드를 수집하는 관점에서 접근할 수 있으며, 리프 노드만을 수집하는 조합이나 분할 문제와 차별화됩니다.

function generateSubsets(elements) {
    const allSubsets = [];
    const currentSubset = [];

    function traverse(startIdx) {
        // 현재 경로를 부분집합으로 저장
        allSubsets.push([...currentSubset]);

        // 시작 인덱스 이후 요소들에 대해 반복
        for (let idx = startIdx; idx < elements.length; idx++) {
            currentSubset.push(elements[idx]);
            traverse(idx + 1);
            currentSubset.pop();
        }
    }

    traverse(0);
    return allSubsets;
}

90. 중복 요소가 포함된 배열의 부분집합

이전 문제와 유사하지만 입력 배열에 중복 요소가 있을 수 있습니다. 결과 집합에서는 동일한 내용의 부분집합이 여러 번 나타나지 않도록 처리해야 합니다.

중복 제거를 위해 먼저 배열을 정렬하고, 같은 레벨에서 이전 요소와 동일한 값을 건너뛰는 로직을 추가합니다.

function generateUniqueSubsets(items) {
    const uniqueSubsets = [];
    const path = [];
    const sortedItems = items.sort((a, b) => a - b);

    function search(startIndex) {
        uniqueSubsets.push([...path]);

        for (let i = startIndex; i < sortedItems.length; i++) {
            // 같은 레벨 내에서 중복되는 요소는 건너뜀
            if (i > startIndex && sortedItems[i] === sortedItems[i - 1]) {
                continue;
            }

            path.push(sortedItems[i]);
            search(i + 1);
            path.pop();
        }
    }

    search(0);
    return uniqueSubsets;
}