trjhtr

Given an array and a value, find all the triplets in the array whose sum is equal to the given value. For example, if the given array is 12, 3, 4, 1, 6, 9 and the given sum is 24, then this is one triplet (12, 3 and 9) which contributes to the total sum of 24.

Solution for given example:

6, 9, 9

6, 6, 12

3, 9, 12

Conditions:

• The ordering of the numbers in the solution does not matter.




• Duplicate triplet is not allowed.




• A number is not allowed to be used multiple times.

This question was asked here.

Here is my code which addresses all the issues. One concern is the code looks a little muddy which I want to avoid in the production grade code. Any constructive feedback is appreciated.

Runtime: O(n2)

GitHub

public class ThreeSum 

 static class Triplet 
 final List<Integer> triplets;

 public Triplet(int x, int y, int z) 
 triplets = Arrays.asList(x, y, z);
 Collections.sort(triplets);
 

 @Override
 public int hashCode() 
 return Objects.hash(triplets.get(0), triplets.get(1), triplets.get(2));
 

 @Override
 public boolean equals(Object o) 
 if (o instanceof Triplet) 

 Triplet other = (Triplet) o;
 return other.triplets.get(0) == this.triplets.get(0) &&
 other.triplets.get(1) == this.triplets.get(1) &&
 other.triplets.get(2) == this.triplets.get(2);
 

 return false;
 

 @Override
 public String toString() 
 return String.format("(%d, %d, %d)", triplets.get(0), triplets.get(1), triplets.get(2));
 
 

 public static Set<Triplet> findTriplets(int numbers, int targetSum) 
 Set<Triplet> triplets = new HashSet<>();

 // insert all pairs in the look up table
 Map<Integer, int> lookup = new HashMap<>();
 for (int i = 0; i < numbers.length - 1; i++) 
 for (int j = i + 1; j < numbers.length; j++) 
 int total = numbers[i] + numbers[j];
 lookup.put(total, new inti, j);
 
 

 // look for the complement, if found viola! here you go with the triplet
 for (int currentIndex = 0; currentIndex < numbers.length; currentIndex++) 
 int complement = targetSum - numbers[currentIndex];

 if (lookup.containsKey(complement)) 
 int indexes = lookup.get(complement);

 if (currentIndex != indexes[0] && currentIndex != indexes[1]) 
 int x = numbers[indexes[0]], y = numbers[indexes[1]];
 triplets.add(new Triplet(x, y, numbers[currentIndex]));
 
 
 

 return triplets;
 

• 
  

  You are storing the integers of a Triplet as a List internally, yet you are not really taking advantage of the interface List's functionality. For example:

  
  
  

  return Objects.hash(triplets.get(0), triplets.get(1), triplets.get(2));
  

  
  
  

  Why not simply do this:

  
  
  

  return triplets.hashCode();
  

  
  
  

  Or, another example:

  
  
  

  return other.triplets.get(0) == this.triplets.get(0) &&
   other.triplets.get(1) == this.triplets.get(1) &&
   other.triplets.get(2) == this.triplets.get(2);
  

  
  
  

  This can be replaced by this:

  
  
  

  return other.triplets.equals(this.triplets);
  

  
  


• 
  

  There's an issue I didn't catch in the old question but which was already present there: Your code doesn't consider the possibility that the same sum is formed by more than one pair of numbers, because you are simply mapping integers to one pair of indices, and if you encounter a pair that adds up to a sum that is already stored in lookup, the old index pair gets overridden.

  
  
  

  A way to overcome this problem could be to map the integers to a List<int>), but this would make things even more complicated, and I think the reason that this would get overly complicated is that you are, in fact, hard-coding a recursive process (first you create the pairs, then from the pairs you create the triplets etc.). You could instead try to write a method that accumulates all possible n-tuplets, with n being any arbitrary positive integer, through recursion, e.g. like this:

  
  
  
  • If n is 1, then return an array/list of all integers
  
  
  • If n is greater than 1, then iterate through the original array and, for every integer in it, combine this integer with all n-1-tuplets formed by the numbers that follow this integer in the array (taking only the following numbers and not the preceding numbers prevents duplicate tuplets that only differ in the order of the integers).
  
  

  I imagine that this would be much easier to code than what you currently have (maybe this is also what you mean by your code being "muddy"), and also much more flexible. True, if it's just about pairs, then it might not be as fast as what you did here, but if it comes to tuplets of more than 2 numbers, I don't think there is much benefit of what you are trying to do here (although this is just a guess, I didn't actually benchmark it).

  
  

Your code is quite inefficient by storing all the sums of pairs into the hashmap.

The memory requirements grow exponentially (adding array entry n adds n more pairs, so it grows in a factorial manner).

You are better off by holding onto a pair only as long as you need it. This can be done by checking all possible additions to that pair at once and then throwing it away.

This is most easily done recursively. You have a set of numbers, and the next number you can either include in your set or not. Repeat this recursively.

Generally, for any given set of array values, you hold onto it only as long as you need it, to try combining it with other items from the array. Once you find a solution you save it. Once you've exhausted all possibilities with that set you throw it away.

public class Recurse 
 static final int target = 24;
 static final int sumCount = 3;
 ArrayList<int> solutions = new ArrayList<int>();

 public void sum(int arr, int arrayIndex, int sum, int indicesSoFar) 
 //you can either include the current value or not

 //first we try skipping it
 if(indicesSoFar.length + arr.length - (arrayIndex + 1) >= sumCount) //only skip if there are enough numbers left
 sum(arr, arrayIndex + 1, sum, indicesSoFar);
 
 //now we try using it
 int val = arr[arrayIndex];
 int added = val + sum;
 if(indicesSoFar.length + 1 == sumCount) //if we use it, it is the last in the set
 if(added == target) // the sum matches, so it is a solution
 int next = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
 next[indicesSoFar.length] = arrayIndex;
 solutions.add(next);
 
 else if(added <= target) //use it if we can (the sum is not too large). This assumes all array values are positive, if negative values allowed, then remove the "if(added <= target)" condition
 int next = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
 next[indicesSoFar.length] = arrayIndex;
 sum(arr, arrayIndex + 1, added, next);
 
 

 public static void main(String args) 
 new Recurse().sum(new int 12, 3, 4, 1, 6, 9, 0, 0, new int[0]);
 

That's all you need when you use the recursive approach. If you add code to print out the results as shown:

public static void main(String args) 
 Recurse recurse = new Recurse();
 int arr = new int 12, 3, 4, 1, 6, 9;
 recurse.sum(arr, 0, 0, new int[0]);
 for(int solution : recurse.solutions) 
 StringBuilder vals = new StringBuilder();
 StringBuilder indices = new StringBuilder();
 for(int index : solution) 
 if(vals.length() > 0) 
 indices.append(", ");
 vals.append(" + ");
 
 indices.append("arr[").append(index).append("]");
 vals.append(arr[index]);
 
 System.out.println("Solution: " + indices + "; " + vals);
 
 

Then it gives you:

Solution: arr[0], arr[1], arr[5] 12 + 3 + 9

Now, according to your requirements you don't want multiple values used, but it's not clear to me if you are only talking about not using the same array element more than once (ie a[i] can appear just once for each i in each solution) or you are talking about using the same number more than once (ie the number x can appear only once in each solution), or you are talking about using the same set of added numbers more than once (the solution x,y,z can appear just once). If you want to handle the other cases, such as to prevent solutions with duplicate values then just check the existing solutions before adding another. Using a HashSet is ideal for this:

public class Recurse 
 static final int target = 24;
 static final int sumCount = 3;
 ArrayList<int> solutions = new ArrayList<int>();
 ArrayList<int> duplicates = new ArrayList<int>();
 HashSet<ArrayList<Integer>> solutionSet = new HashSet<ArrayList<Integer>>();

 public void sum(int arr, int arrayIndex, int sum, int indicesSoFar) 
 //you can either include the current value or not

 //first we try skipping it
 if(indicesSoFar.length + arr.length - (arrayIndex + 1) >= sumCount) //only skip if there are enough numbers left
 sum(arr, arrayIndex + 1, sum, indicesSoFar);
 
 //now we try using it
 int val = arr[arrayIndex];
 int added = val + sum;
 if(indicesSoFar.length + 1 == sumCount) //if we use it, it is the last
 if(added == target) 
 int next = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
 next[indicesSoFar.length] = arrayIndex;
 ArrayList<Integer> solution = new ArrayList<Integer>();
 for(int i : next) 
 solution.add(arr[i]);
 
 Collections.sort(solution);
 if(!solutionSet.contains(solution)) 
 solutionSet.add(solution);
 solutions.add(next);
 else 
 duplicates.add(next);
 
 
 else if(added <= target) //this assumes all array values are positive, if negative allowed, then no "if(added < target)" here
 int next = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
 next[indicesSoFar.length] = arrayIndex;
 sum(arr, arrayIndex + 1, added, next);
 
 

 public static void main2(String args) 
 new Recurse().sum(new int 12, 3, 4, 1, 6, 9, 0, 0, new int[0]);
 

 public static void main(String args) 
 Recurse recurse = new Recurse();
 int arr = new int 12, 3, 4, 1, 6, 3, 9;
 recurse.sum(arr, 0, 0, new int[0]);
 for(int i = 0; i < 2; i++) 
 String label = i == 0 ? "Solution: " : "Duplicate: ";
 ArrayList<int> solutionList = i == 0 ? recurse.solutions : recurse.duplicates;
 for(int solution : solutionList) 
 StringBuilder vals = new StringBuilder();
 StringBuilder indices = new StringBuilder();
 for(int index : solution) 
 if(vals.length() > 0) 
 indices.append(", ");
 vals.append(" + ");
 
 indices.append("arr[").append(index).append("]");
 vals.append(arr[index]);
 
 System.out.println(label + indices + "; " + vals);
 
 
 

Which gives:

Solution: arr[0], arr[5], arr[6]; 12 + 3 + 9
Duplicate: arr[0], arr[1], arr[6]; 12 + 3 + 9