18. 4Sum

public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        var rs = new List<IList<int>>();
        Array.Sort(nums);
        Helper(rs, nums, target, 4, 0, new List<int>());
        return rs;
    }
    private void Helper(List<IList<int>> rs, int[] nums, long target, int k, int index, List<int> subList) {
        if (k == 2) {
            int l = index;
            int r = nums.Length - 1;
            while (l < r) {
                long sum = nums[l] + nums[r];
                if (sum == target) {
                    subList.Add(nums[l]);
                    subList.Add(nums[r]);
                    rs.Add(new List<int>(subList));
                    subList.RemoveAt(subList.Count - 1);
                    subList.RemoveAt(subList.Count - 1);
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    while (l < r && nums[r - 1] == nums[r]) {
                        r--;
                    }
                    l++;
                    r--;
                } else if (sum < target) {
                    l++;
                } else {
                    r--;
                }
            }
        } else {
            for (int i = index; i < nums.Length - k + 1; i++) {
                if (i != index && nums[i] == nums[i - 1]) {
                    continue;
                }
                subList.Add(nums[i]);
                Helper(rs, nums, target - nums[i], k - 1, i + 1, subList);
                subList.RemoveAt(subList.Count - 1);
            }
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<vector<int>> FourSum(vector<int>& nums, int target) {
        var rs = new List<vector<int>>();
        sort(nums.begin(), nums.end());
        Helper(rs, nums, target, 4, 0, new List<int>());
        return rs;
    }
    private void Helper(List<vector<int>> rs, vector<int>& nums, long target, int k, int index, List<int> subList) {
        if (k == 2) {
            int l = index;
            int r = nums.size() - 1;
            while (l < r) {
                long sum = nums[l] + nums[r];
                if (sum == target) {
                    subList.push_back(nums[l]);
                    subList.push_back(nums[r]);
                    rs.push_back(new List<int>(subList));
                    subList.RemoveAt(subList.size() - 1);
                    subList.RemoveAt(subList.size() - 1);
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    while (l < r && nums[r - 1] == nums[r]) {
                        r--;
                    }
                    l++;
                    r--;
                } else if (sum < target) {
                    l++;
                } else {
                    r--;
                }
            }
        } else {
            for (int i = index; i < nums.size() - k + 1; i++) {
                if (i != index && nums[i] == nums[i - 1]) {
                    continue;
                }
                subList.push_back(nums[i]);
                Helper(rs, nums, target - nums[i], k - 1, i + 1, subList);
                subList.RemoveAt(subList.size() - 1);
            }
        }
    }
}

public class Solution {
    int len = 0;

    public List<List<Integer>> fourSum(int[] nums, int target) {
        len = nums.length;
        Arrays.sort(nums);
        return kSum(nums, target, 4, 0);
    }

    private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (index >= len) {
            return res;
        }

        if (k == 2) {
            int i = index, j = len - 1;
            while (i < j) {
                // Find a pair
                if (target - nums[i] == nums[j]) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(target - nums[i]);
                    res.add(temp);
                    // Skip duplicates
                    while (i < j && nums[i] == nums[i + 1]) i++;
                    while (i < j && nums[j - 1] == nums[j]) j--;
                    i++;
                    j--;
                } else if (target - nums[i] > nums[j]) {
                    i++;
                } else {
                    j--;
                }
            }
        } else {
            for (int i = index; i < len - k + 1; i++) {
                // Use current number to reduce kSum into k-1Sum
                ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k - 1, i + 1);
                if (temp != null) {
                    // Add previous results
                    for (List<Integer> t : temp) {
                        t.add(0, nums[i]);
                    }
                    res.addAll(temp);
                }
                // Skip duplicates
                while (i < len - 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
            }
        }
        return res;
    }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
    const n = nums.length;
    const ans = [];
    if (n < 4) {
        return ans;
    }
    nums.sort((a, b) => a - b);
    for (let i = 0; i < n - 3; ++i) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        for (let j = i + 1; j < n - 2; ++j) {
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue;
            }
            let [k, l] = [j + 1, n - 1];
            while (k < l) {
                const x = nums[i] + nums[j] + nums[k] + nums[l];
                if (x < target) {
                    ++k;
                } else if (x > target) {
                    --l;
                } else {
                    ans.push([nums[i], nums[j], nums[k++], nums[l--]]);
                    while (k < l && nums[k] === nums[k - 1]) {
                        ++k;
                    }
                    while (k < l && nums[l] === nums[l + 1]) {
                        --l;
                    }
                }
            }
        }
    }
    return ans;
};

def fourSum(self, nums, target):
    nums.sort()
    results = []
    self.findNsum(nums, target, 4, [], results)
    return results

def findNsum(self, nums, target, N, result, results):
    if len(nums) < N or N < 2: return

    # solve 2-sum
    if N == 2:
        l,r = 0,len(nums)-1
        while l < r:
            if nums[l] + nums[r] == target:
                results.append(result + [nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
                while r > l and nums[r] == nums[r + 1]:
                    r -= 1
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1
    else:
        for i in range(0, len(nums)-N+1):   # careful about range
            if target < nums[i]*N or target > nums[-1]*N:  # take advantages of sorted list
                break
            if i == 0 or i > 0 and nums[i-1] != nums[i]:  # recursively reduce N
                self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
    return

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    res := [][]int{}
    for i:=0; i<len(nums)-3; i++ {
        for i>0 && i<len(nums) && nums[i]==nums[i-1] {
            i++
        }
        for j:=i+1; j<len(nums); j++ {
            for j>i+1 && j<len(nums) && nums[j]==nums[j-1] {
                j++
            }
            start:=j+1
            end:=len(nums)-1
            for start<end {
                if (nums[start]+nums[end]+nums[i]+nums[j])<target {
                    start++
                    for start< len(nums) && nums[start]==nums[start-1] {
                        start++
                    }
                } else if (nums[start]+nums[end]+nums[i]+nums[j])>target {
                    end--
                    for end>0 && nums[end]==nums[end+1] {
                        end--
                    }
                } else {
                    res = append(res, []int{nums[i], nums[j], nums[start], nums[end]})
                    start++
                    end--
                    for start<len(nums) && nums[start]==nums[start-1] {
                        start++
                    }
                    for end>0 && nums[end]==nums[end+1] {
                        end--
                    }
                }
            }
        }
    }
    return res
}

Метод FourSum:

Этот метод инициализирует основной процесс поиска, создавая список rs для хранения результатов.

Массив nums сортируется для упрощения дальнейшей логики.

Затем вызывается вспомогательный метод Helper с параметрами: результатами, отсортированным массивом, целевым значением, количеством элементов для поиска (в данном случае 4), начальным индексом и пустым списком для временного хранения текущего поднабора.

Метод Helper:

Этот метод рекурсивно находит наборы чисел, которые соответствуют заданному количеству k и суммируются до указанного целевого значения target.

База рекурсии (k == 2): Когда требуется найти пары чисел, функция использует двухуказательный подход. l начинает с начального индекса, r — с конца массива. В цикле проверяется сумма чисел на этих позициях:

Если сумма равна target, текущая пара добавляется в временный список subList, и результат добавляется в основной список rs. После добавления результаты очищаются для следующего возможного набора.

Если сумма меньше target, увеличивается индекс l, чтобы попробовать большее число.

Если сумма больше target, уменьшается индекс r, чтобы попробовать меньшее число.

Рекурсивный вызов (k > 2): При большем количестве элементов для поиска (например, 4) метод перебирает элементы массива начиная с указанного индекса. Для каждого элемента:

Если текущий элемент такой же, как предыдущий, пропускается, чтобы избежать дублирования.

Текущий элемент добавляется в subList, и вызывается рекурсивно с уменьшением k на 1 и обновлением целевого значения (target - nums[i]).

После возвращения из рекурсии элемент удаляется из subList для возможности обработки следующих комбинаций.

Временная и пространственная сложность:

Временная сложность: О(n^3), так как в самом худшем случае каждая из рекурсий может быть вызвана до трех уровней вложенности, где n — длина массива nums.

Пространственная сложность: O(n), включая список для хранения подмножеств и рекурсивный стек.