class Solution{
    public:
        vector<vector<int>> foursum(vector<int> &nums, int target){
            sort(begin(nums), end(nums));
            return ksum(nums, target, 0 ,4);
        }
        vector<vector<int>> ksum(vector<int> &nums, long long target, int start, int k){
            vector<vector<int>> res;
            if(start == nums.size()) return res;
            long long avg = target/k;
            if(nums[start] > avg || nums.back()<avg) return res;

            if(k==2) return twosum(nums, target, start);

            for(int i = start; i<nums.size(); i++){
                if(i == start || nums[i]!= nums[i-1]){
                    for(auto &subset : ksum(nums, target - nums[i], i+1, k-1)){
                        res.push_back({nums[i]});
                        res.back().insert(end(res.back()), begin(subset), end(subset));
                    }
                }
            }
            return res;

            
        }
        vector<vector<int>> twosum(vector<int> &nums, long long target, int start){
            vector<vector<int>> res;
            unordered_set<long long> s;
            for(int i = start; i<nums.size();i++){
                if(res.empty() || res.back()[1]!= nums[i]){
                    if(s.count(target- nums[i])){
                        res.push_back({int(target-nums[i]),nums[i]});
                    }
                }
                 s.insert(nums[i]);

            }
        return res;        
    }
        
        
};
// TC : o(n^3) or o(n^(k-1)) in general
// SC : O(n)