C++ recursive solution


  • 0
    U
    class Solution {
    private:
        int target, size;
        vector<vector<int> > result;
        vector<int> tmp, nums;
        
    public:
        vector<vector<int> > fourSum(vector<int>& nums, int target) {
            int depth = 4;
            if (nums.size() >= depth) {
                this->target = target;
                this->nums = nums;
                this->size = this->nums.size();
                std::sort(this->nums.begin(), this->nums.end());
                depth--;
                for (int i = 0; i < this->size - depth; i++) {	
                	if (isTargetExist(i, depth)) {
                	    if (i == 0 || this->nums[i-1] != this->nums[i]) {
                            findTargets(depth, i, 0);
                        }	
    	         }
                }    
            }
            return result;
        }
        
    private:
    	    
       bool isTargetExist(int i, int depth) {
           int sum1 = nums[i];
           int sum2 = sum1;
           for(depth; depth > 0; depth-- ) {
               sum1 += nums[size - depth];
        	   sum2 += nums[++i];
    	}
            return sum1 >= target && sum2 <= target;
        }
    	
        void findTargets(int depth, int index, int sum) {
            if (depth == 0) {
                sum += nums[index];
                if (sum == target) {
                    tmp.push_back(nums[index]);
                    result.push_back(tmp);
                    tmp.pop_back();   
                }
                return;
            }
    	depth--;
            sum += nums[index];
            tmp.push_back(nums[index]);
            for (int i = index + 1; i < this->size - depth; i++) {
                if ((i == index + 1) || (nums[i - 1] != nums[i])) {
                    findTargets(depth, i, sum);
                }
            }
            tmp.pop_back();
        }
    };
    
    

Log in to reply
 

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