[Question]: Find Quads that add up to a target value4 Sum

##### Approach# using the 4 pointers

Two pointers a & b are fixed and we have two moving pointers c and d. where c starts from b + 1 and d is start from last index

```
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
let len = nums.count
guard len >= 4 else { return [] }// minimum 4 items required for 4 sum
var result = [[Int]]()
let sort = nums.sorted()
for a in 0..<(len - 1) where a == 0 || sort[a] != sort[a-1] { // if sort[a] == sort[a-1] discard the loop // a is fix pointer
for b in (a + 1)..<len where b == a + 1 || sort[b] != sort[b-1] {// if sort[b] == sort[b-1] discard the loop // b is fix pointer
var c = b + 1, d = len - 1// c pointer is b+1 which is movable
while c < d {// As array is sorted check if c pointer doesn't jump
let val = (a: sort[a], b: sort[b], c: sort[c], d: sort[d])
let sum = (val.a + val.b + val.c + val.d)
if sum == target { result.append([val.a,val.b,val.c,val.d]) }// add result to the array as we found the desired sum
if sum < target {
while sort[c] == val.c, c < d { c += 1 }// increment c pointer as we get lesser sum
} else {
while sort[d] == val.d, d > b { d -= 1 }// decrement d pointer which is the last
}
}
}
}
return result
}
let fourSumInputArray = [1,0,-1,0,-2,2]
let fourSumOutputArray = fourSum(fourSumInputArray, 0)
print("Output array-->", fourSumOutputArray) //[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
```

##### Complexity Analysis

**Time Complexity: **O(N^{3}), where N = size of the array.**Reason: **Each of the pointers c and d, is running for approximately N times. And both the pointers k and l combined can run for approximately N times including the operation of skipping duplicates. So the total time complexity will be O(N^{3}).

**Space Complexity: ** O(n) where we stores the result.