0015. 3Sum.md

C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> path;
        nSum(nums, res, path, 0, 0, 3);
        return res;
    }

    void nSum(vector<int>& nums, vector<vector<int>>& res, vector<int>& path, int start, int target, int n) {
        if(n == 2) {
            int l = start;
            int r = nums.size() - 1;
            while(l < r) {
                int sum = nums[l] + nums[r];
                if(sum == target) {
                    vector<int> comb = path;
                    comb.push_back(nums[l]);
                    comb.push_back(nums[r]);
                    res.push_back(comb);
                    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 < nums.size(); i++) {
            if(i > start && nums[i] == nums[i - 1]) continue;
            path.push_back(nums[i]);
            nSum(nums, res, path, i + 1, target - nums[i], n - 1);
            path.pop_back();
        }
    }
};

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) => a -  b);
    const res = [];
    
    function nSum(arr, target, result, n) {
        if(n === 2) {
            twoSum(arr, target, result);
            return;
        }
        
        for(let i = 0; i < arr.length; i++) {
            while(arr[i] === arr[i - 1]) i++;
            //...result includes all previous numbers that already been picked up from original array
            nSum(arr.slice(i + 1), target - arr[i], [...result, arr[i]], n - 1);
        }
    }
    
    function twoSum(arr, target, result) {
        let low = 0, high = arr.length - 1;
        while(low < high) {
            let sum = arr[low] + arr[high];
            if(sum === target) {
                //res is containing result array from nSum function, and two more numbers from this function
                res.push([...result, arr[low], arr[high]]);
                while(arr[low] === arr[low + 1]) low++;
                while(arr[high] === arr[high - 1]) high--;
                low++;
                high--;
            }
            else if(sum < target) {
                low++;
            }
            else {
                high--;
            }
        }
    }
    
    nSum(nums, 0, [], 3);
    return res;
};