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

• ProgramCreek

• YouTube

Examples

Example 1

Input: nums = [-1, 0, 1, 2, -1, -4]

Output: [[-1, -1, 2], [-1, 0, 1]]

Example 2

Example 3

Solutions

Solution 1

/**
 * 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();
        }
    }
}

Solution 2

Solution 3

Follow up