Ksum 问题

Ksum，用backtracking来做，转换成1sum or 2sum，

3Sum: https://leetcode.com/problems/3sum/description/

4Sum: https://leetcode.com/problems/4sum/description/

class Solution {
public:
    
    void find1Sum(vector<vector<int>> &allcomb, vector<int> &comb, vector<int>& nums, int target, int start){
        for(int i=start; i<nums.size(); i++){
            if(nums[i] == target){
                comb.push_back(nums[i]);
                allcomb.push_back(comb);
                comb.pop_back();
            }
        }
    }
    
    void find2Sum(vector<vector<int>> &allcomb, vector<int> &comb, vector<int>& nums, int target, int start){
        int left = start, right = nums.size()-1;
        while(left < right){
            int sum = nums[left] + nums[right];
            if(sum == target){
                comb.push_back(nums[left]);
                comb.push_back(nums[right]);
                allcomb.push_back(comb);
                comb.pop_back();
                comb.pop_back();
                left++; right--;
                while(nums[left] == nums[left-1]) left++;
                while(nums[right] == nums[right+1]) right--;
            }
            else if(sum < target){
                left++;
            }
            else{
                right--;
            }
        }
    }
    
    void find4Sum(vector<vector<int>> &allcomb, vector<int> &comb, vector<int>& nums, int target, int start, int k){
        if(k <= 0){
            return;
        }
        
        else if(k == 1){
            find1Sum(allcomb, comb, nums, start, target);
            return;
        }
        else if(k == 2){
            find2Sum(allcomb, comb, nums, target, start);
            return;
        }
        
        for(int i=start; i<=nums.size()-k; i++){
            if(i > start && nums[i] == nums[i-1]){
                continue;
            }
            
            comb.push_back(nums[i]);
            find4Sum(allcomb, comb, nums, target-nums[i], i+1, k-1);
            comb.pop_back();
        }
    }
    
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> allcomb;
        if(nums.size() < 4){
            return allcomb;
        }
        
        vector<int> comb;
        sort(nums.begin(), nums.end());
        find4Sum(allcomb, comb, nums, target, 0, 4);
        return allcomb;
    }
};