--

leetcode 018: 4 sum

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

---

---

problem:

---

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

---

---

start code (c++)

---

 
class Solution {
public:
    bool isMatch(string s, string p) {
        
    }
};

---

---

solution:

我的思路：
要想实现 4 sum, 先实现 3 sum, 然后实现 2 sum,

---

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums = sorted(nums)
        solution = self.sum4(nums, target)
        # need to remove duplicate
        size = len(solution)
        for s in range(size-1, 0, -1):
            if solution[s] in solution[:s]:
                solution.pop(s)
        return solution
        
    def sum4(self, nums, target):
        if len(nums) < 4:
            return []
        s1 = self.sum3(nums[:-1], target - nums[-1])
        s2 = self.sum4(nums[:-1], target)
        for x in s1:
            x.append(nums[-1])
        return s1 + s2
    
    def sum3(self, nums, target):
        if len(nums) < 3:
            return []
        s1 = self.sum2(nums[:-1], target - nums[-1])
        s2 = self.sum3(nums[:-1], target)
        for x in s1:
            x.append(nums[-1])
        return s1 + s2
    
    def sum2(self, nums, target):
        # nums already sorted
        solution = []
        if len(nums) < 2:
            return solution
        i = 0;
        j = len(nums) -1
        while i < j:
            if nums[i] + nums[j] == target:
                solution.append([nums[i],nums[j]])
                i += 1
            else:
                if nums[i] + nums[j] > target:
                    j -= 1
                else:
                    i += 1
        return solution
    
            
    
        

---