Provided a 1D array of integers, find all combinations of 3 values from this set such that: a+b+c=0

Ok, I can't figure out where I what I am doing wrong in my code. I have tried debugging but without knowing what they are asking me to fix it's kind of hard to just go from that. Any advice on how to correct this would be greatly appreciated.

function [S] = ThreeSum(i, j, k)

    for i=0;
        i < S;

        for j = i + 1;
            j < S;

                for k = j + 1;
                    k < S;

                        if a(i) + a(j) + a(k) == 0;
                        end
                end
        end
    end
end

Answer 1

[G A]

if A is your 1D array, than you can use:

B=combntns(A,3);

C=sum(B,2);

D=B(~C,:);

[Sean de Wolski]

+1 Never heard of that before, sweet!

[Larry]

Thank you for not being condesending and actually helping me learn something about matlab!

[Jan]

Does somebody know a more efficient solution if the input is large, e.g. 1e6 elements?

[John D'Errico]

I'm sorry Larry. But this did not teach you anything about matlab. If you don't understand the very basics of matlab, you will never get anywhere. Learn to use the language. Start reading the tutorials.

[John D'Errico]

Jan - Assume exact integer inputs, so there is no need to worry chasing after floating point issues. If the number of elements are truly large, on the order of 1e6, then there will be a huge number of solutions, too many to enumerate in the case you give. For example, suppose that your candidate set is composed of a=-5e5:5e5. At a guess, there will be roughly 5e11 solutions. They will be fairly easy to enumerate in the case of consecutive integers, all of which lie inside a polygon on a canted plane in R^3. But suppose you were given a less uniform set of integers? Even an intermediate size problem, with perhaps 5K to 50K elements will still cause serious difficulties if brute force is applied, although you could possibly succeed there with a semi-recursive solution and a loop. That is, given the value of x(1) = a(1), you now need only to find all pairs of elements that sum to -x(1). Repeat for every possible a(i), and you are done.

[Jan]

Thanks, John. After sorting the array a binary search is helpful to reduce the search tree substantially. I though of Bruno's http://www.mathworks.com/matlabcentral/fileexchange/17818-all-permutations-of-integers-with-sum-criteria , but this does not catch the problem directly. If runtime will be a criterium in Cody, this would be a nice question.

Answer 2

[John D'Errico]

What exactly is the purpose of statements like this:

i < s;

What do you think they do?

Next, what do you think MATLAB does when it sees a loop like this:

for i = 0;
end

How many times does it execute that loop?

I think you need to look at the help for for. Read the documentation. Look at the examples. Don't just write code as you might imagine it will work, perhaps what might work in some other language, because your imagination will probably be wrong.

And, oh, by the way, matlab indexing starts at 1, NOT at 0. You cannot try to find the vector element a(0) and not expect to get an error.

Finally, some think that it is poor programming practice to use i and j as loop variables, as i and j are already defined in MATLAB as the imaginary unit for complex numbers, sqrt(-1). Personally, I like to use i and j for that purpose myself, and I tend not to work in the complex domain, so it it not an issue for me.

Answer 3

[Walter Roberson]

Your code uses "S" and "a" without defining them.

Your line

i < S;

will compare i to the non-existent S, causing an error. But if S had been defined, whatever the result of the comparison was, it would just throw away the result because of the semi-colon at the end of the line.

Your line

for i=0;

runs a loop with "i" set only to the value 0, and no other value.

I would suggest you need to review the syntax for MATLAB "for" loops: it is not the same as the syntax for C.

[Jan]

Let me mention, that "for i=0; i<S; <LoopBody>" is even not valid C.