LeetCode 求和問題總結：2Sum, 3Sum, 4Sum, K Sum 通用解法

前言

LeetCode 中的 2Sum、3Sum、4Sum 及其變體（如 3Sum Closest）是經典面試題，核心考察排序後雙指針與去重技巧。本文將這些問題推廣為通用的 K Sum 問題，給出遞歸解法並具體套用至 K=2,3,4。

K Sum 問題定義

給定整數數組 nums（長度 N）與目標值 target，找出所有不重複的 K 元組，使其和等於 target。數組可能包含重複元素，結果需去重。

去重策略

1. 排序後雙指針跳過相同值：在指針移動時，若下一個元素與當前相同則繼續移動。
2. 使用 set<vector<int>> 自動去重：將合法解存入集合，最後轉為向量輸出。

通用遞歸框架 (K Sum)

void kSum(vector<int>& nums, int target, int k, int start, vector<int>& path, vector<vector<int>>& res) {
    if (k == 2) { // 2Sum 雙指針
        int l = start, r = nums.size() - 1;
        while (l < r) {
            int sum = nums[l] + nums[r];
            if (sum == target) {
                path.push_back(nums[l]);
                path.push_back(nums[r]);
                res.push_back(path);
                path.pop_back(); path.pop_back();
                while (l < r && nums[l] == nums[l+1]) ++l;
                while (l < r && nums[r] == nums[r-1]) --r;
                ++l; --r;
            } else if (sum < target) ++l;
            else --r;
        }
        return;
    }
    for (int i = start; i <= (int)nums.size() - k; ++i) {
        if (i > start && nums[i] == nums[i-1]) continue; // 去重
        path.push_back(nums[i]);
        kSum(nums, target - nums[i], k - 1, i + 1, path, res);
        path.pop_back();
    }
}

具體應用

代碼示例：3Sum

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for (int i = 0; i < (int)nums.size(); ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int l = i + 1, r = nums.size() - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                res.push_back({nums[i], nums[l], nums[r]});
                while (l < r && nums[l] == nums[l+1]) ++l;
                while (l < r && nums[r] == nums[r-1]) --r;
                ++l; --r;
            } else if (sum < 0) ++l;
            else --r;
        }
    }
    return res;
}

總結

掌握「排序 + 固定前 K-2 個數 + 雙指針」模板，配合去重邏輯，即可高效解決所有 K Sum 系列問題。