Iteratively find all combinations of size k of an array of characters (N choose K)

I am currently working on this problem as a personal project.

Basically:

• Given an array of elements, e.g. E = {1,2,a,b} and
• Given a number, K, e.g. K = 2
• I want to return all Combinations of E of size K (E choose K)
• E.g. {{1,1}, {1,2}, {1,a}, {1,b}, {2,1}, ... , {b,1}, {b,2}, {b,a}, {b,b}}

I have already achieved this recursively using the following function:

char[] pool = new char[]{'1', '2', '3'};

public void buildStringRec(char[] root, int pos, int length){
    for(char c : pool){
        char[] newRoot = root.clone();
        newRoot[pos] = c;
        if(pos+1 < length){
            buildStringRec(newRoot, pos+1, length);
        } else{
            System.out.println(String.valueOf(root));
        }
    }
}

Where pool is E and length is K.

So we would call: buildStringRec(new char[2], 0, 2); and get

11
12
13
21
22
23
31
32
33

Can this be done iteratively? I have been trying to wrap my head around how I would do this with variable lengths.

Any help would be appreciated! If need be, I can post my code as it is, but it changes so frequently due to my retrying that it's almost useless as soon as I post it.

Also, I do not want to do this using Apache or String Builder as I want to understand the CONCEPT of how to do it. I am not simply asking for code. Pseudo-code is just fine as long as it is clearly explained.

Thanks!

EDIT

I am using this site to test out all options presented to me: https://ideone.com/k1WIa6
Feel free to fork it and try it out!

Here's another iterative solution:

You can create an array of integers of size K to act as a counter recording how far you are through the combinations, and a char array to store the current combination.

After printing each one, move on to the next combination by increasing one of the counter values, and if it "overflows" by reaching a value equal to the number of elements in E, then reset it to zero and perform a carry by incrementing the counter in the next position, checking for overflows there too and so on. Kind of like an odometer in a car, except that the numbers are tied to values in E. Once the last position overflows then you have generated all the possible combinations.

I've incremented the counters starting from the last value in the array and moving downwards to get the same output as in your example, but that isn't necessary of course. The algorithm doesn't check for duplicates.

You don't have to store an array of chars with the current combination, you could just re-generate it each time in a for loop based on the counters, but that might be less efficient. This approach only updates the values that change.

public static void buildStrings(char[] root, int length)
{
    // allocate an int array to hold the counts:
    int[] pos = new int[length];
    // allocate a char array to hold the current combination:
    char[] combo = new char[length];
    // initialize to the first value:
    for(int i = 0; i < length; i++)
        combo[i] = root[0];

    while(true)
    {
        // output the current combination:
        System.out.println(String.valueOf(combo));

        // move on to the next combination:
        int place = length - 1;
        while(place >= 0)
        {
            if(++pos[place] == root.length)
            {
                // overflow, reset to zero
                pos[place] = 0;
                combo[place] = root[0];
                place--; // and carry across to the next value
            }
            else
            {
                // no overflow, just set the char value and we're done
                combo[place] = root[pos[place]];
                break;
            }
        }
        if(place < 0)
            break;  // overflowed the last position, no more combinations
    }
}

ideone.com demo