Find unique triplets

Question

In my function I have to find all unique triplets to given numbers K from given array. It finds all triplets but many of them are there twice or more like 1 1 5 is same as 1 5 1 or 5 1 1 and etc.

Can somebody help me with this?

int triplet(int *array, int size, int K) {
  int i, j, k;
  int found = 0; /* triplets whose sum is equal to K */
  for(i = 0; i < size; i++) {
    for (j = 0; j < size; j++) {    
      for (k = 0; k < size; k++) {
        if(array[i] + array[j] + array[k] == K) {
          printf("Triplet Found : %d, %d, %d\n", array[i], array[j], array[k]);
          found++;
        }           
      }
    }
  }
  return found;
}

score 0 · Answer 1 · answered Dec 01 '16 at 13:46

To exclude combinations you could try the following change:

int triplet(int *array, int size, int K) {
  int i, j, k;
  int found = 0; /* triplets whose sum is equal to K */
  for(i = 0; i < size; i++) {
    for (j = i; j < size; j++) {    
      for (k = j; k < size; k++) {
        if(array[i] + array[j] + array[k] == K) {
          printf("Triplet Found : %d, %d, %d\n", array[i], array[j], array[k]);
          found++;
        }           
      }
    }
  }
  return found;
}

Notice the j = i and k = j statements in the for loop declarations. This way you will skip the possible duplicates for your case and yet cover all variations of the i, j and k variables.

score 0 · Accepted Answer · answered Dec 01 '16 at 13:47

0

You should not repeat already processed combinations; a possible solution would be to start each for cycle from de previous ID + 1, like so:

for(i = 0; i < size; i++) {
 for (j = i+1; j < size; j++) {    
  for (k = j+1; k < size; k++) {
    if(array[i] + array[j] + array[k] == K) {
      printf("Triplet Found : %d, %d, %d\n", array[i], array[j], array[k]);
      found++;
    }           
  }
}

setting j = i + 1; you prevent same-element triplets!

answered Dec 01 '16 at 13:47

Giovazz89

391
3
12

1

Using `id + 1` would not work for the example provided by the OP (1 1 5) – Bojan B Dec 01 '16 at 13:50
I think that it was an output example, not an input, and it would work: – Giovazz89 Dec 01 '16 at 14:02
array[0] + array[1] + array[2] == K – Giovazz89 Dec 01 '16 at 14:02

Find unique triplets

2 Answers2