> 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/2-sum-all-pair-i.md).

# 2 Sum All Pair I

Find all pairs of elements in a given array that sum to the given target number. Return all the pairs of indices.

**Assumptions**

* The given array is not null and has length of at least 2.

**Examples**

* A = {1, 3, 2, 4}, target = 5, return \[\[0, 3], \[1, 2]]
* A = {1, 2, 2, 4}, target = 6, return \[\[1, 3], \[2, 3]]

Solution: HashMap

Use hashmap to track indices of values

Iterate through array, if (target - current index value) exists within the map. Add (Current index, other indices) into result.

```
public List<List<Integer>> allPairs(int[] array, int target){
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Map<Integer, List<Integer>> map = new HashSet<Integer, List<Integer>>();
    
    for (int i = 0; i < array.length; i++){
        //get other half of pair
        List<Integer>indices = map.get(target - array[i]);
        
        if (indices != null){
            for (int j: indices){
                results.add(Arrays.asList(j, i); //add pair to result
            {
        }
        
        if (!map.containsKey(array[i])){ // if value at current index not in map
            map.put(array[i], new ArrayList<Integer>()); // make new slot to store indices for current value
        }
        map.get(array[i]).add(i); // add current index
    }
    return result;
}
```

Time Comp: O(N) when hashmap is empty, approaches O(N^2) near the end.

Space Comp: O(N^2) worst case if every element included in result.