My solution is not very fast, 32ms, but it's universal for nSum problems, and easy to understand!


  • 0
    P

    This is the first version which costs 152ms.

    void nSum(vector<int>& nums, int target, int n, vector<vector<int>>& ans, vector<int>& res, int start, int len) {
        if (n == 0) {
            if (target == 0)
                ans.push_back(res);
            return;
        }
        for (int i = start;i <= len - n;++i) {
            if (nums[i] * n > target || nums.back() * n < target)
                break;
            res.push_back(nums[i]);
            nSum(nums,target-nums[i],n-1,ans,res,i+1,len);
            res.pop_back();
            while (i+1 <= len - n && nums[i] == nums[i+1])
                ++i;
        }
    }
    
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        vector<int> res;
        sort(nums.begin(),nums.end());
        nSum(nums,target,4,ans,res,0,nums.size());
        return ans;
    }
    

    This is the second version, much faster, 32ms! I believe it can be optimized to run faster!

    void nSum(vector<int>& nums, int target, int n, vector<vector<int>>& ans, vector<int>& res, int start, int len) {
        if (n == 1) {
            if (binary_search(nums.begin()+start,nums.end(),target)) {
                res.push_back(target);
                ans.push_back(res);
                res.pop_back();
            }
            return;
        }
        for (int i = start;i <= len - n;++i) {
            if (nums[i] * n > target || nums.back() * n < target)
                break;
            res.push_back(nums[i]);
            nSum(nums,target-nums[i],n-1,ans,res,i+1,len);
            res.pop_back();
            while (i+1 <= len - n && nums[i] == nums[i+1])
                ++i;
        }
    }
    
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        vector<int> res;
        sort(nums.begin(),nums.end());
        nSum(nums,target,4,ans,res,0,nums.size());
        return ans;
    }
    

    I always love this kind of easy code, my coding style is programming different problems in a common paradigm, and this one is simple standard backtracking with pruning!


  • -1
    S

    The code for turning is not right. Suppose you have {-6,-4,-3,-1,2,5,8}.
    The first two operands is {-6,-1}, you get the last two operands by recursing with value of {2,5}.
    When the first two operands is {-3,-4}, you get the last two operands still by recursing with value of {2,5}, which would waste a lot of time if there are n operands, and result in exceeding time. It is better idea to have a hashmap to store the value returned by recursing.


  • 0
    J

    This is indeed a pretty neat solution. However, it fails to pass 3Sum due to Time Limit Exceeded. I guess there might be no any large testcase for 4Sum to expose this issue.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.