K Sum

September 03, 2022

1 - Two Sum

• Sort
• Use a low and high pointer
• Use while to skip duplicates

vector<vector<int>> TwoSum(vector<int>& nums, long long target, int idx){
    vector<vector<int>> res;
    int lo = idx;
    int hi = nums.size()-1;
    while(lo < hi){
        long long sum = nums[lo] + nums[hi];
        if(sum < target){
            lo ++;
        }else if(sum > target){
            hi --;
        }else{
            res.push_back({nums[lo], nums[hi]});
            while(lo < hi and nums[lo+1] == nums[lo]) lo++;
            while(hi > lo and nums[hi-1] == nums[hi]) hi--;
            lo ++; hi --;
        }
    }
    return res;
}

2 - K Sum

• Recursion to reduce to twoSum case
• Remember to skip duplicates during the kSum i loop
• Remember to use long long for target

class Solution {
public:
    vector<vector<int>> TwoSum(vector<int>& nums, long long target, int idx){
        vector<vector<int>> res;
        int lo = idx;
        int hi = nums.size()-1;
        while(lo < hi){
            long long sum = nums[lo] + nums[hi];
            if(sum < target){
                lo ++;
            }else if(sum > target){
                hi --;
            }else{
                res.push_back({nums[lo], nums[hi]});
                while(lo < hi and nums[lo+1] == nums[lo]) lo++;
                while(hi > lo and nums[hi-1] == nums[hi]) hi--;
                lo ++; hi --;
            }
        }
        return res;
    }
        
    
    vector<vector<int>> kSum(vector<int>& nums, int n, int idx, long long target){
        if(n == 2){
            return TwoSum(nums, target, idx);
        }else{
            vector<vector<int>> res;
            for(int i = idx; i < nums.size(); i++){
                if(i != idx and nums[i] == nums[i-1])
                    continue;
                vector<vector<int>> sub = kSum(nums, n-1, i+1, target-(long)nums[i]);
                for(auto& vec : sub){
                    vec.push_back(nums[i]);
                    res.push_back(vec);
                }
            }
            return res;
        }
    }
    
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        return kSum(nums, 4, 0, target);
    }
};