LeetCode 4Sum (JavaScript)

링크 : https://leetcode.com/problems/4sum/submissions/1832172032/

문제 설명

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

• 1 <= nums.length <= 200
• 109 <= nums[i] <= 109
• 109 <= target <= 109

---

문제 풀이

backtracking으로 문제를 접근 -> 시간 초과 발생 (더보기 클릭)

nums에서 1개씩 선택을 해가며 총 4개(selected)가 되었을 때 중복이 안된다면 answer에 추가하는 형식으로 backtracking을 구현

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    const answer = [];
    nums.sort((a, b) => a - b);

    const selected = [];
    const used = new Set();

    const backtracking = (index, sum, depth) => {
        if (sum === target && depth === 4) {
            if (!used.has(selected.join(''))) {
                used.add(selected.join(''));
                answer.push([...selected]);
            }
            return;
        }

        if (depth < 4 && nums.length - index < 4 - depth) {
            return;
        }

        for (let i = index; i < nums.length; i++) {
            selected.push(nums[i]);
            backtracking(i + 1, sum + nums[i], depth + 1);
            selected.pop(nums[i]);
        }
    }

    backtracking(0, 0, 0);

    return answer;
};

3Sum과 같은 문제 https://kuh97.tistory.com/entry/LeetCode-3Sum-JavaScript 참고

4sum -> (2개의 포인터 고정, 2개는 Two Pointer이용)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    const answer = [];
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        for (let j = i + 1; j < nums.length - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue;
            }

            let [left, right] = [j + 1, nums.length - 1];

            const sum = nums[i] + nums[j];

            while (left < right) {
                const total = sum + nums[left] + nums[right];

                if (total === target) {
                    answer.push([nums[i], nums[j], nums[left], nums[right]]);

                    while (left < right && nums[left] === nums[left + 1]) {
                        left++;
                    }

                    while (left < right && nums[right] === nums[right - 1]) {
                        right--;
                    }

                    left++;
                    right--;
                } else if (total < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }

    return answer;
};

---

결론

Backtracking으로 문제를 접근했지만 depth가 4이고 nums가 많아질 경우 최악의 경우 O(n^4)의 시간이 걸리게 됨

-> 3Sum 문제를 응용한 투 포인터 방식으로 접근하여 해결, O(n^3)의 시간 복잡도를 가짐