> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/3sum.md).

# 15. 3Sum

### Description

Given an array `nums` of *n* integers, are there elements *a*, *b*, *c* in `nums` such that *a* + *b* + *c* = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

### Constraints

* `0 <= nums.length <= 3000`
* `-105 <= nums[i] <= 105`

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/3sum/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** nums = \[-1, 0, 1, 2, -1, -4]

**Output:** \[\[-1, -1, 2], \[-1, 0, 1]]
{% endtab %}

{% tab title="Example 2" %}
**Input:** nums = \[0]

**Output:** \[]
{% endtab %}

{% tab title="Example 3" %}
**Input:** nums = \[]

**Output:** \[]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> resultList = new HashSet();
        if(nums == null || nums.length < 3) {
            new ArrayList(resultList);
        }
        
        helper(nums, resultList, new LinkedList<Integer>(), 0, 0);
        
        return new ArrayList(resultList);
    }
    
    private void helper(int[] nums,
                        Set<List<Integer>> resultList,
                        LinkedList<Integer> currList,
                        int start,
                        int sum) {
        if(currList.size() == 3) {
            if(sum == 0) {
                List<Integer> tmpList = new ArrayList(currList);
                Collections.sort(tmpList);
                resultList.add(tmpList);
            }
            return;
        }
        for(int i = start; i < nums.length; i++) {
            currList.add(nums[i]);
            helper(nums, resultList, currList, i+1, sum+nums[i]);
            currList.removeLast();
        }
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        int n = nums.length;
        Arrays.sort(nums);
        for(int i = 0; i < n; i++) {
            int val = nums[i];
            int l = i+1;
            int r = n-1;
            while(l < r) {
                int sum = val + nums[l] + nums[r];
                if(sum == 0) {
                    res.add(Arrays.asList(val, nums[l++], nums[r--]));
                }
                else if(sum < 0) l++;
                else if(sum > 0) r--;
            }
        }
        return new ArrayList<>(res);
    }
}
```

{% endtab %}

{% tab title="Solution 3" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i-1] == nums[i]) continue;
            int l = i+1, r = nums.length-1;
            while(l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if(sum < 0) l++;
                else if(sum > 0) r--;
                else {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while(l < r && nums[l] == nums[l+1]) l++;
                    while(l < r && nums[r] == nums[r-1]) r--;
                    l++;
                    r--;
                }
            }
        }
        return res;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*