12ms KSum, c++ code
Thanks to the posts from others, it really helped me understand the problem! \nI really liked @rikimberley's example for validity checking at levels of K higher
Thanks to the posts from others, it really helped me understand the problem! \nI really liked @rikimberley's example for validity checking at levels of K higher than 2 and I liked the approaches I've seen for turning the problem into a KSum problem. Now I won't have to re-write my answer if they make a 5 sum problem!\n\n```\nclass Solution {\nprivate:\n    // Valid for K >= 2\n    void KSum(int k, vector<int>& nums, int l, int r, int target, vector<vector<int>>& retVal, vector<int>& cur, int ci ) \n    {\n        int i, mn, mx;\n        int km1 = k - 1;\n\n        if ( r-l+1 < k ) return;\n        \n        while ( l < r )\n        {\n            mn = nums[l];\n            mx = nums[r];\n            \n            // If K minus 1 largest + min < target, move to larger\n            if ( ( mn + km1*mx ) < target ) l++;\n            // If K minus 1 smaller + max > target, move to smaller\n            else if ( ( km1*mn + mx ) > target ) r--;\n            // If K * min > target, stop looking\n            else if ( k*mn > target ) break;\n            // If K * min == target, reached the threshold, check then stop looking\n            else if ( k*mn == target )\n            {\n                if ( ( l + km1 <= r ) && ( mn == ( nums[l+km1] ) ) )\n                {\n                    for ( i = 0; i < k; i++ ) cur[ci+i] = mn;\n                    retVal.push_back( cur );\n                }\n                break;\n            }\n            // If K * max < target, stop looking\n            else if ( k*mx < target ) break;\n            // If K * max == target, reached the threshold, check then stop looking\n            else if ( k*mx == target )\n            {\n                if ( ( l <= r - km1 ) && ( mx == ( nums[r-km1] ) ) )\n                {\n                    for ( i = 0; i < k; i++ ) cur[ci+i] = mx;\n                    retVal.push_back( cur );\n                }\n                break;                \n            }\n            // If K == 2, we found a match!\n            else if ( k == 2 )\n            {\n                cur[ci] = mn;\n                cur[ci+1] = mx;\n                retVal.push_back( cur );\n                l++;\n                while ( ( l < r ) && ( nums[l] == mn ) ) l++;\n                r--;\n                while ( ( l < r ) && ( nums[r] == mx ) ) r--;\n            }\n            // Otherwise, convert the problem to a K-1 problem\n            else\n            {\n                cur[ci] = mn;\n                KSum( km1, nums, ++l, r, target - mn, retVal, cur, ci+1 );\n                while ( ( l < r ) && ( nums[l] == nums[l-1] ) ) l++;\n            }\n        }\n    }\n\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) \n    {\n        vector<vector<int>> lRetVal;\n        vector<int> lQuad( 4, 0 ); // Pre-allocate the size of the result\n\n        // Sort to provide a mechanism for avoiding duplicates\n        sort( nums.begin(), nums.end() );\n        \n        KSum( 4, nums, 0, nums.size()-1, target, lRetVal, lQuad, 0 );\n\n        return( lRetVal );        \n    }\n};
[]