Share my K SUM c++ solution


  • 1
    Z
    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            sort(nums.begin(),nums.end());
            k=4;
            tmp=vector<int>(k,0);
            dfs(nums,target,k,0);
            return res;
        }
    private:
        vector<vector<int>> res;
        vector<int> tmp;
        int k;
        void dfs(vector<int> &nums, int target,int n,int start){
            if(n==2){
                int end=nums.size()-1;
                while(start<end){
                    if(nums[start]+nums[end]==target){
                        tmp[k-2]=nums[start];
                        tmp[k-1]=nums[end];
                        res.push_back(tmp);
                        while(++start<end&&nums[start-1]==nums[start]);
                        while(--end>start&&nums[end+1]==nums[end]);
                    }
                    else if(nums[start]+nums[end]>target)end--;
                    else start++;
                }
            }
            else{
                int len=nums.size()-n;
                while(start<=len){
                    tmp[k-n]=nums[start];
                    dfs(nums,target-nums[start],n-1,start+1);
                    while(++start<=len&&nums[start-1]==nums[start]);
                }
            }
        }
    };

Log in to reply
 

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