Loop through an array, check if a+b+c == A but avoid rechecking c+b+a etc

Question

I've got this nailed down but it's inefficient given it goes back and checks the same thing (a+b+c and a+c+b and the other variants instead of just a+b+c).

Any way to avoid that? My code is as follows:

int array[8]={4,5,6,0,3,2,1,9};
int i = 0, j = 0, k = 0, nmbr = 10;
for(i=0; i<8; ++i){
        for(j=0; j<8; ++j){
                for(k=0; k<8; ++k){
                    if((array[i]+array[j]+array[k]) == nmbr)
                        printf("%d is found with %d + %d + %d\n", nmbr, array[i], array[j], array[k]);
                }
        }
}

Any help would be appreciated.

I would really encourage you to not use "magic numbers" in your loop conditional statements. Use array.size() instead. This makes your program much more flexible and easier to maintain when your array changes size. — Evan Bechtol, Apr 26 '15 at 14:49
@EvanBechtol: since the question is tagged `c`, there's no such thing as `.size()`. Instead you have to rely on defines `#define ARRAY_SIZE (8)`, or this kind of constructs: http://stackoverflow.com/questions/37538/how-do-i-determine-the-size-of-my-array-in-c — Gauthier, Apr 27 '15 at 12:20

score 2 · Answer 1 · answered Apr 25 '15 at 13:27

Start j from i and k from j, or if duplication of indexes are not permitted in the solution, then let j start from i+1 and k from j+1.

int array[8]={4,5,6,0,3,2,1,9};
int i = 0, j = 0, k = 0, nmbr = 10;
for(i=0; i<8; ++i){
        for(j=i; j<8; ++j){
                for(k=j; k<8; ++k){
                    if((array[i]+array[j]+array[k]) == nmbr)
                        printf("%d is found with %d + %d + %d\n", nmbr, array[i], array[j], array[k]);
                }
        }
}

score 2 · Answer 2 · answered Apr 25 '15 at 13:27

Change:

for(i=0; i<8; ++i){
        for(j=0; j<8; ++j){
                for(k=0; k<8; ++k){

to:

for(i=0; i<8-2; ++i){
        for(j=i+1; j<8-1; ++j){
                for(k=j+1; k<8; ++k){

Note: this assumes that i, j, k need to be distinct. It's easy to change though if this is not a requirement:

for(i=0; i<8; ++i){
        for(j=i; j<8; ++j){
                for(k=j; k<8; ++k){

score 2 · Answer 3 · answered Apr 25 '15 at 13:27

2

Start the second loop with j = i, and the third loop with k = j ( + 1 in each if you can't have twice the same number in the sum)

answered Apr 25 '15 at 13:27

Gauthier

40,309
11
63
97

Loop through an array, check if a+b+c == A but avoid rechecking c+b+a etc

3 Answers3