> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/2-sum/3-sum.md).

# 3 Sum

Determine if there exists three elements in a given array that sum to the given target number. Return all the triple of values that sums to target.

**Assumptions**

* The given array is not null and has length of at least 3
* No duplicate triples should be returned, order of the values in the tuple does not matter

**Examples**

* A = {1, 2, 2, 3, 2, 4}, target = 8, return \[\[1, 3, 4], \[2, 2, 4]]

Solution: left right pinch at every index

Iterate through array

only check for first appearance of each element

for each element check for (x + y = target - element)

If found: 

1. add (element, x, y) to results
2. skip trailing duplicate x, continue searching

```
public class Solution {
  public List<List<Integer>> allTriples(int[] array, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(array);
    for (int i = 0; i < array.length - 2; i++){
      //ignore duplicates
      if (i > 0 && array[i] == array[i - 1]){
        continue;
      }

      int left = i + 1;
      int right = array.length - 1;
      while (left < right){
        int tmp = array[left] + array[right];
        if (tmp + array[i] == target){
          result.add(Arrays.asList(array[i], array[left], array[right]));
          left++;
          //ignore duplciate js
          while( left < right && array[left] == array[left - 1]){
            left++;
          }
        } else if (tmp + array[i] < target){
          left++;
        } else {
          right--;
        }
      }
    }
    return result;
  }
}

```

Time Comp: Two iterations O(N^2)

Space Comp: O(N) result storage