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 для хранения результатов.

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

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

Метод Helper:

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

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

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

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

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

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

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

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

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

Временная и пространственная Complexity:

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

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