Monday, December 15, 2014

Find possible triangle triplets

Woke up this morning I decided to find some problems that are not on LeetCode. Here is one from Careercup.

I used backtracking for this problem. However, it may not be the best solution since the complexity is O(n!).

"Given a array of positive integers, find all possible triangle triplets that can be formed from this array. 
eg: 9 8 10 7 
ans: 9 8 10, 9 8 7, 9 10 7, 7 8 10 
Note : array not sorted, there is no limit on the array length"

import java.util.ArrayList;
import java.util.Arrays;


public class PossibleTriangle {
 public ArrayList> possibleTriangle(int[] nums)
 {
  ArrayList> rst = new ArrayList>();
  if (nums == null || nums.length == 0)
   return rst;
  ArrayList triplets = new ArrayList();
  Arrays.sort(nums);
  getTriangle(rst, triplets, nums, 0);
  return rst;
 }
 private void getTriangle(ArrayList> rst, ArrayList triplets, 
   int[] nums, int start)
 {
  if (triplets.size() == 3 && triplets.get(0) + triplets.get(1) > triplets.get(2))
   rst.add(new ArrayList (triplets));
  for (int i = start; i < nums.length; i++)
  {
   if (i != start && nums[i] == nums[i - 1])
    continue;
   triplets.add(nums[i]);
   getTriangle(rst, triplets, nums, i + 1);
   triplets.remove(triplets.size() - 1);
  }
 }
 public void printList(ArrayList> rst)
 {
  for (int i = 0; i < rst.size(); i++)
   System.out.println(rst.get(i));
 }

}
public class TriangleTester {

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  //int[] nums = {6, 6, 6, 6, 6, 6, 6, 6};
  int[] nums = {1, 2, 3, 6, 6, 7, 2, 9, 8};
  PossibleTriangle pt = new PossibleTriangle();
  ArrayList> rst = pt.possibleTriangle(nums);
  pt.printList(rst);

 }

}

No comments:

Post a Comment