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

Question

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!

Zane

Strictly speaking {1,1} is not a subset of {1,2,3} (or rather it is the same set as {1}, since sets can't contain the same element multiple times - those would be multisets). Thus {1,1} should not be part of the output if you actually want to return "the set of subsets of E of size K". However you seem to be happy with the result (which is printing out all Elements of E x E), so i guess thats just an issue with the terminology. – Selfgoverned

Ya, that's my fault for messing up the terminology. I will edit what I can to make it more clear as to what I want. – Zane

@HW This wouldn't really be a Combinations either would it as possible combinations wouldn't include {1,1}... Perhaps this is more of a "Recursive Cross Multiplication"? So for length 3, I would be using ((ExE)xE) to get my values? What do you think? – Zane

Yes, the "Recoursive Cross Multiplication" is called cartesian product though (or cartesian power) - refer to en.wikipedia.org/wiki/Cartesian_product - and can be written as E^K (or ExE for K=2). – Selfgoverned

Answer 1

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

Cown

Answer 2

Recursive solution

As for me, it looks like recursive solution is the best option here.
You can replace cloning your path array with stack to improve performance:

char[] pool = new char[]{'1', '2', '3'};
Stack<int> stack = new Stack<int>();

// Actually, resulting length should be the same length as pool array
int length = pool.length;

public void buildStringRec(int pos)
{
    if (length == pos + 1) 
    {
        System.out.println(String.valueOf(root));
        return;
    }

    for(char c : pool){
        stack.Push(c);
        buildStringRec(pos + 1);
        stack.Pop(c);
    }
}

Iterative solution

Let's suppose that, for some reason, you need to do this iteratively.
I am sure that there is a better solution. However, that's the best I could make.

You can rephrase your task to another one:

How to output ALL numbers in base N of length N.

Let's suppose you have an array of length 3: {'a', 1, 'z'}.
Your desirable answer will be:

a-a-a    a-a-1    a-a-z
a-1-a    a-1-1    a-1-z
a-z-a    a-z-1    a-z-z
1-a-a    1-a-1    1-a-z

Now, let's look at the indices of these values:

0-0-0    0-0-1    0-0-2
0-1-0    0-1-1    0-1-2
0-2-0    0-2-1    0-2-2 
2-0-0    2-0-1    2-0-2

Actually, that's a consecutive numbers in base 3: 000, 001, 002, 010, 011, 012, 020, 021, 022, 200, 201, 202.

Keep in mind the formula of their count: base ^ length. In our case, length == base. Thus, it is base ^ base.

Now, our task is becoming easier:

int[] toBase(long bs, long value)
{ 
    int[] result = new int[bs];
    for (long i = bs - 1; i >= 0; i--)
    {
        result[i] = (int)(value % bs);
        value = value / bs;
    }
    return result;
}

long Pow(long a, long b)
{
    long result = 1;
    for (int i = 0; i < b; i++) result *= a;
    return result;
}

char[] pool = new char[] {'a', 'b', 'c'};

void outputAll()
{
    long n = pool.Length;
    for (long i = 0; i < Pow(n, n); i++)
    {
        int[] indices = toBase(n, i);
        for (int j = 0; j < n; j++)
            Console.Write("{0} ", pool[indices[j]]);
        Console.WriteLine();
    }
}

Of course, there could be some optimizations:

• There is no need to calculate toBase every time. It is easier and more performant to initiate from 000 and every time calculate the next number.
• You can change Pow function to use fast exponentiation by squaring algorithm etc.

This is just an example provided to explain an approach.

Keep in mind that array of length 3 will have only 27 such combinations. However, an array of length 7 will have 823543. It grows exponentially.

The working sample

Here is a DotNetFiddle working Demo.

Just change pool array values in order to get your results. In here and in all examples above I have used C#. It can be easily converted to C++ :)

As for me, it works great for length up to 7 (about 1 - 1.5 seconds).
Of course, you will need to remove console output to get such results. Console output works really slow.

Curry

Your Recursion using the Stack seems to work nicely. However, it's not consistently better than the char[] method I had before. You can use the following link to see what I mean. Just change minLength and maxLength to different values to get different runtimes at the bottom. ideone.com/k1WIa6 I don't understand how to use your Base-n method for the problem I am trying to solve. – Zane

Answer 3

A simple Iterative solution would be to

• create an array to hold an index for each character for the length of output needed
• Then iterate through the indexes and print each character from the pool corresponding to the indexes
• Then increment the last index of the indexes array
• if the last index is equal to the pool length
  • set it to zero
  • increment the previous index
  • repeat with previous index until you reach the beginning of the array or an index does not equal the pool length

Below is some sample code in Java

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

public void buildStrings(int length){

  int[] indexes = new int[length];
  // In Java all values in new array are set to zero by default
  // in other languages you may have to loop through and set them.

  int pMax = pool.length;  // stored to speed calculation
  while (indexes[0] < pMax){ //if the first index is bigger then pMax we are done

    // print the current permutation
    for (int i = 0; i < length; i++){
      System.out.print(pool[indexes[i]]);//print each character
    }
    System.out.println(); //print end of line

    // increment indexes
    indexes[length-1]++; // increment the last index
    for (int i = length-1; indexes[i] == pMax && i > 0; i--){ // if increment overflows 
      indexes[i-1]++;  // increment previous index
      indexes[i]=0;   // set current index to zero  
    }     
  }
}

Erenow

This is incorrect, this include combinations with repeated indices. – Jolynjolynn

Answer 4

Iterative solution

Here is an algorithm I developed in C/C++, with iterative functions and with constant spacial complexity

It handles indexes of a C array so it can be used for any type of data, here an array of characters (C++ string) which can be a string of digits

Function 1: generate all possible combinations

// str: string of characters or digits
void GenerateAll(string str, int k)
{
    int n = str.length();

    // initialization of the first subset containing k elements
    int *sub_tab = new int[k];
    for(int j(0); j<k; ++j)
    {
        sub_tab[j] = j;
    }

    do
    {   
        // Convert combination to string
        char *sub_str = new char[k];
        for(int j(0); j<k; ++j)
        {
            sub_str[j] = str[sub_tab[j]];
        }
        // Print combinations of each set
        Combinations(sub_str);
        // get next sub string
    } while (AddOne(sub_tab, k-1, n) == true);
    
    delete [] sub_tab;      
}

Function 2: Generate all combinations for each set

void Combinations(string str)
{
    int n = str.length();

    // Compute all factorials from 0 to n
    unsigned long int * factorials = new unsigned long int[n+1];
    factorials[0] = 1;
    for(int i = 1; i<=n; ++i)
        factorials[i] = factorials[i-1] * i;

    char *tab = new char[n];

    // Initialization with the first combination 0123...n-1
    for(int i(0); i<n; ++i)
    {
        tab[i] = i;
        cout << str[i] << " ";
    }
    cout << endl;

    for(unsigned long int i(1); i < factorials[n]; ++i)
    {
        for (int j(0); j < n; ++j)
        {
            if(i % factorials[n-j-1] == 0)
            {
                // increment tab[j] (or find the next available)
                SetNextAvailable(tab, j, n);
            }
        }
        for (int j(0); j < n; ++j)
        {
            cout << str[tab[j]] << " "; 
        }
        cout << endl;
    }

    delete [] factorials;
}

Function SetNextAvailable()

void SetNextAvailable(char *tab, int j, int n)
{
    bool finished;
    do
    {
        finished = true;
        ++(*(tab+j));
        if (*(tab+j) == n) *(tab+j) = 0;
        for (int i(0); i < j; ++i)
        {
            if ( *(tab+i) == *(tab+j) )
            {
                finished = false;
                break;
            }
        }
    } while(finished == false);
}

Function AddOne()

bool AddOne(int *tab, int k, int n)
{
    int i;
    for(i=k; i>=0; --i)
    {
        if(((++tab[i]) + (k-i)) != n)
            break;
    }
    if(i == -1)
        return false;
    else
    {
        for(int j=i+1; j<=k; ++j)
        {
            tab[j] = tab[j-1] + 1;
        }
        return true;
    }
}

Singularity

Sorry, I edited the wrong answer when trying to edit my own one, and I've rollback it :) – Jolynjolynn

Answer 5

Here is a go impl for combination via iteration, in input order (for both combinations & items within each combination).

---

Code (go)

package combination_util

import (
    "fmt"
    "golang.org/x/exp/constraints"
)

// count combinations, via iteration, apply given handler on each combination,
func CombInOrderCountViaIter[T constraints.Ordered](is []T, m int, h HandlerCount[T]) int {
    n := len(is)
    if m < 0 || n < m { // invalid
        return 0
    }
    seq := 0
    if m == 0 { // corner: empty,
        h(is, nil, &seq)
        return 1
    }

    indices := make([]int, m)
    for i := 0; i < m; i++ {
        indices[i] = i
    }

    li := m - 1 // last index to move,
    maxIdx := n - 1
    h(is, indices, &seq)
    endIdxForFirst := n - m

    if n > m {
    outer:
        for {
            if indices[li] < maxIdx {
                indices[li]++
                h(is, indices, &seq)
            } else if m > 1 {
                curIdx, preIdx := li, li-1
                for {
                    indices[preIdx]++

                    if indices[curIdx]-indices[preIdx] == 1 {
                        h(is, indices, &seq)
                        if preIdx == 0 && indices[0] == endIdxForFirst { // done
                            break outer
                        }
                    } else {
                        for i, delta := curIdx, 1; i < m; i, delta = i+1, delta+1 {
                            indices[i] = indices[preIdx] + delta
                        }
                        h(is, indices, &seq)
                        break
                    }

                    curIdx--
                    preIdx--
                }
            } else {
                break
            }
        }
    }

    return seq
}

// items are int sequence start from 0, e.g index,
func CombInOrderCountViaIterAsIndex(n, m int, h HandlerCount[int]) int {
    is := GenInputAsIndex(n)
    return CombInOrderCountViaIter(is, m, h)
}

// count & print,
func CombInOrderCountAndPrintViaIterAsIndex(n, m int) int {
    PrintInputAsIndex(n, m, true)
    return CombInOrderCountViaIterAsIndex(n, m, HandlerCountImplPrint[int])
}

// count & print pattern,
func CombInOrderCountAndPrintPatternViaIterAsIndex(n, m int) int {
    PrintInputAsIndex(n, m, true)
    return CombInOrderCountViaIterAsIndex(n, m, HandlerCountImplPrintPattern[int])
}


// extract combination from indices & original input,
func indicesToComb[T constraints.Ordered](is []T, flags []int) []T {
    m := len(flags)
    comb := make([]T, m)
    for i := 0; i < m; i++ {
        comb[i] = is[flags[i]]
    }
    return comb
}

// print input & m,
func PrintInput[T constraints.Ordered](is []T, m int, prependNewLine bool) {
    prefix := ""
    if prependNewLine {
        prefix = "\n"
    }
    fmt.Printf("%s%v, m = %d:\n", prefix, is, m)
}

// print input & m, as indices,
func PrintInputAsIndex(n, m int, prependNewLine bool) {
    is := GenInputAsIndex(n)
    PrintInput[int](is, m, prependNewLine)
}

// generate input of size n, as indices start from 0,
func GenInputAsIndex(n int) []int {
    is := make([]int, n)
    for i := 0; i < n; i++ {
        is[i] = i
    }
    return is
}


const (
    BlackSquare = '◼'
    WhiteSquare = '◻'
)

/* handler types */
type HandlerCount[T constraints.Ordered]   func(is []T, indices []int, seq *int)

/* handler impl */
// count handler - print,
func HandlerCountImplPrint[T constraints.Ordered](is []T, indices []int, seq *int) {
    comb := indicesToComb(is, indices)
    fmt.Printf("\t(%d)\t%v\n", *seq, comb)
    *seq++
}

// count handler - print pattern (white & black square),
func HandlerCountImplPrintPattern[T constraints.Ordered](is []T, indices []int, seq *int) {
    n := len(is)
    pattern := make([]rune, n)

    for i := 0; i < n; i++ {
        pattern[i] = WhiteSquare
    }
    for _, index := range indices {
        pattern[index] = BlackSquare
    }

    fmt.Printf("\t%s\t(%d)\n", string(pattern), *seq)
    *seq++
}

---

Test

func main() {
    CombInOrderCountAndPrintViaIterAsIndex(5, 3)
    CombInOrderCountAndPrintPatternViaIterAsIndex(10, 5)
}

---

Output

• print combination, via CombInOrderCountAndPrintViaIterAsIndex()
  n = 5, m = 3, generated input = [0 1 2 3 4]:

    (0) [0 1 2]
    (1) [0 1 3]
    (2) [0 1 4]
    (3) [0 2 3]
    (4) [0 2 4]
    (5) [0 3 4]
    (6) [1 2 3]
    (7) [1 2 4]
    (8) [1 3 4]
    (9) [2 3 4]
  

• print pattern, via CombInOrderCountAndPrintPatternViaIterAsIndex()
  n = 10, m = 5, generated input = [0 1 2 3 4 5 6 7 8 9]:

    ◼◼◼◼◼◻◻◻◻◻  (0)
    ◼◼◼◼◻◼◻◻◻◻  (1)
    ◼◼◼◼◻◻◼◻◻◻  (2)
    ◼◼◼◼◻◻◻◼◻◻  (3)
    ◼◼◼◼◻◻◻◻◼◻  (4)
    ◼◼◼◼◻◻◻◻◻◼  (5)
    ◼◼◼◻◼◼◻◻◻◻  (6)
    ◼◼◼◻◼◻◼◻◻◻  (7)
    ◼◼◼◻◼◻◻◼◻◻  (8)
    ◼◼◼◻◼◻◻◻◼◻  (9)
    ◼◼◼◻◼◻◻◻◻◼  (10)
    ◼◼◼◻◻◼◼◻◻◻  (11)
    ◼◼◼◻◻◼◻◼◻◻  (12)
    ◼◼◼◻◻◼◻◻◼◻  (13)
    ◼◼◼◻◻◼◻◻◻◼  (14)
    ◼◼◼◻◻◻◼◼◻◻  (15)
    ◼◼◼◻◻◻◼◻◼◻  (16)
    ◼◼◼◻◻◻◼◻◻◼  (17)
    ◼◼◼◻◻◻◻◼◼◻  (18)
    ◼◼◼◻◻◻◻◼◻◼  (19)
    ◼◼◼◻◻◻◻◻◼◼  (20)
    ◼◼◻◼◼◼◻◻◻◻  (21)
    ◼◼◻◼◼◻◼◻◻◻  (22)
    ◼◼◻◼◼◻◻◼◻◻  (23)
    ◼◼◻◼◼◻◻◻◼◻  (24)
    ◼◼◻◼◼◻◻◻◻◼  (25)
    ◼◼◻◼◻◼◼◻◻◻  (26)
    ◼◼◻◼◻◼◻◼◻◻  (27)
    ◼◼◻◼◻◼◻◻◼◻  (28)
    ◼◼◻◼◻◼◻◻◻◼  (29)
    ◼◼◻◼◻◻◼◼◻◻  (30)
    ◼◼◻◼◻◻◼◻◼◻  (31)
    ◼◼◻◼◻◻◼◻◻◼  (32)
    ◼◼◻◼◻◻◻◼◼◻  (33)
    ◼◼◻◼◻◻◻◼◻◼  (34)
    ◼◼◻◼◻◻◻◻◼◼  (35)
    ◼◼◻◻◼◼◼◻◻◻  (36)
    ◼◼◻◻◼◼◻◼◻◻  (37)
    ◼◼◻◻◼◼◻◻◼◻  (38)
    ◼◼◻◻◼◼◻◻◻◼  (39)
    ◼◼◻◻◼◻◼◼◻◻  (40)
    ◼◼◻◻◼◻◼◻◼◻  (41)
    ◼◼◻◻◼◻◼◻◻◼  (42)
    ◼◼◻◻◼◻◻◼◼◻  (43)
    ◼◼◻◻◼◻◻◼◻◼  (44)
    ◼◼◻◻◼◻◻◻◼◼  (45)
    ◼◼◻◻◻◼◼◼◻◻  (46)
    ◼◼◻◻◻◼◼◻◼◻  (47)
    ◼◼◻◻◻◼◼◻◻◼  (48)
    ◼◼◻◻◻◼◻◼◼◻  (49)
    ◼◼◻◻◻◼◻◼◻◼  (50)
    ◼◼◻◻◻◼◻◻◼◼  (51)
    ◼◼◻◻◻◻◼◼◼◻  (52)
    ◼◼◻◻◻◻◼◼◻◼  (53)
    ◼◼◻◻◻◻◼◻◼◼  (54)
    ◼◼◻◻◻◻◻◼◼◼  (55)
    ◼◻◼◼◼◼◻◻◻◻  (56)
    ◼◻◼◼◼◻◼◻◻◻  (57)
    ◼◻◼◼◼◻◻◼◻◻  (58)
    ◼◻◼◼◼◻◻◻◼◻  (59)
    ◼◻◼◼◼◻◻◻◻◼  (60)
    ◼◻◼◼◻◼◼◻◻◻  (61)
    ◼◻◼◼◻◼◻◼◻◻  (62)
    ◼◻◼◼◻◼◻◻◼◻  (63)
    ◼◻◼◼◻◼◻◻◻◼  (64)
    ◼◻◼◼◻◻◼◼◻◻  (65)
    ◼◻◼◼◻◻◼◻◼◻  (66)
    ◼◻◼◼◻◻◼◻◻◼  (67)
    ◼◻◼◼◻◻◻◼◼◻  (68)
    ◼◻◼◼◻◻◻◼◻◼  (69)
    ◼◻◼◼◻◻◻◻◼◼  (70)
    ◼◻◼◻◼◼◼◻◻◻  (71)
    ◼◻◼◻◼◼◻◼◻◻  (72)
    ◼◻◼◻◼◼◻◻◼◻  (73)
    ◼◻◼◻◼◼◻◻◻◼  (74)
    ◼◻◼◻◼◻◼◼◻◻  (75)
    ◼◻◼◻◼◻◼◻◼◻  (76)
    ◼◻◼◻◼◻◼◻◻◼  (77)
    ◼◻◼◻◼◻◻◼◼◻  (78)
    ◼◻◼◻◼◻◻◼◻◼  (79)
    ◼◻◼◻◼◻◻◻◼◼  (80)
    ◼◻◼◻◻◼◼◼◻◻  (81)
    ◼◻◼◻◻◼◼◻◼◻  (82)
    ◼◻◼◻◻◼◼◻◻◼  (83)
    ◼◻◼◻◻◼◻◼◼◻  (84)
    ◼◻◼◻◻◼◻◼◻◼  (85)
    ◼◻◼◻◻◼◻◻◼◼  (86)
    ◼◻◼◻◻◻◼◼◼◻  (87)
    ◼◻◼◻◻◻◼◼◻◼  (88)
    ◼◻◼◻◻◻◼◻◼◼  (89)
    ◼◻◼◻◻◻◻◼◼◼  (90)
    ◼◻◻◼◼◼◼◻◻◻  (91)
    ◼◻◻◼◼◼◻◼◻◻  (92)
    ◼◻◻◼◼◼◻◻◼◻  (93)
    ◼◻◻◼◼◼◻◻◻◼  (94)
    ◼◻◻◼◼◻◼◼◻◻  (95)
    ◼◻◻◼◼◻◼◻◼◻  (96)
    ◼◻◻◼◼◻◼◻◻◼  (97)
    ◼◻◻◼◼◻◻◼◼◻  (98)
    ◼◻◻◼◼◻◻◼◻◼  (99)
    ◼◻◻◼◼◻◻◻◼◼  (100)
    ◼◻◻◼◻◼◼◼◻◻  (101)
    ◼◻◻◼◻◼◼◻◼◻  (102)
    ◼◻◻◼◻◼◼◻◻◼  (103)
    ◼◻◻◼◻◼◻◼◼◻  (104)
    ◼◻◻◼◻◼◻◼◻◼  (105)
    ◼◻◻◼◻◼◻◻◼◼  (106)
    ◼◻◻◼◻◻◼◼◼◻  (107)
    ◼◻◻◼◻◻◼◼◻◼  (108)
    ◼◻◻◼◻◻◼◻◼◼  (109)
    ◼◻◻◼◻◻◻◼◼◼  (110)
    ◼◻◻◻◼◼◼◼◻◻  (111)
    ◼◻◻◻◼◼◼◻◼◻  (112)
    ◼◻◻◻◼◼◼◻◻◼  (113)
    ◼◻◻◻◼◼◻◼◼◻  (114)
    ◼◻◻◻◼◼◻◼◻◼  (115)
    ◼◻◻◻◼◼◻◻◼◼  (116)
    ◼◻◻◻◼◻◼◼◼◻  (117)
    ◼◻◻◻◼◻◼◼◻◼  (118)
    ◼◻◻◻◼◻◼◻◼◼  (119)
    ◼◻◻◻◼◻◻◼◼◼  (120)
    ◼◻◻◻◻◼◼◼◼◻  (121)
    ◼◻◻◻◻◼◼◼◻◼  (122)
    ◼◻◻◻◻◼◼◻◼◼  (123)
    ◼◻◻◻◻◼◻◼◼◼  (124)
    ◼◻◻◻◻◻◼◼◼◼  (125)
    ◻◼◼◼◼◼◻◻◻◻  (126)
    ◻◼◼◼◼◻◼◻◻◻  (127)
    ◻◼◼◼◼◻◻◼◻◻  (128)
    ◻◼◼◼◼◻◻◻◼◻  (129)
    ◻◼◼◼◼◻◻◻◻◼  (130)
    ◻◼◼◼◻◼◼◻◻◻  (131)
    ◻◼◼◼◻◼◻◼◻◻  (132)
    ◻◼◼◼◻◼◻◻◼◻  (133)
    ◻◼◼◼◻◼◻◻◻◼  (134)
    ◻◼◼◼◻◻◼◼◻◻  (135)
    ◻◼◼◼◻◻◼◻◼◻  (136)
    ◻◼◼◼◻◻◼◻◻◼  (137)
    ◻◼◼◼◻◻◻◼◼◻  (138)
    ◻◼◼◼◻◻◻◼◻◼  (139)
    ◻◼◼◼◻◻◻◻◼◼  (140)
    ◻◼◼◻◼◼◼◻◻◻  (141)
    ◻◼◼◻◼◼◻◼◻◻  (142)
    ◻◼◼◻◼◼◻◻◼◻  (143)
    ◻◼◼◻◼◼◻◻◻◼  (144)
    ◻◼◼◻◼◻◼◼◻◻  (145)
    ◻◼◼◻◼◻◼◻◼◻  (146)
    ◻◼◼◻◼◻◼◻◻◼  (147)
    ◻◼◼◻◼◻◻◼◼◻  (148)
    ◻◼◼◻◼◻◻◼◻◼  (149)
    ◻◼◼◻◼◻◻◻◼◼  (150)
    ◻◼◼◻◻◼◼◼◻◻  (151)
    ◻◼◼◻◻◼◼◻◼◻  (152)
    ◻◼◼◻◻◼◼◻◻◼  (153)
    ◻◼◼◻◻◼◻◼◼◻  (154)
    ◻◼◼◻◻◼◻◼◻◼  (155)
    ◻◼◼◻◻◼◻◻◼◼  (156)
    ◻◼◼◻◻◻◼◼◼◻  (157)
    ◻◼◼◻◻◻◼◼◻◼  (158)
    ◻◼◼◻◻◻◼◻◼◼  (159)
    ◻◼◼◻◻◻◻◼◼◼  (160)
    ◻◼◻◼◼◼◼◻◻◻  (161)
    ◻◼◻◼◼◼◻◼◻◻  (162)
    ◻◼◻◼◼◼◻◻◼◻  (163)
    ◻◼◻◼◼◼◻◻◻◼  (164)
    ◻◼◻◼◼◻◼◼◻◻  (165)
    ◻◼◻◼◼◻◼◻◼◻  (166)
    ◻◼◻◼◼◻◼◻◻◼  (167)
    ◻◼◻◼◼◻◻◼◼◻  (168)
    ◻◼◻◼◼◻◻◼◻◼  (169)
    ◻◼◻◼◼◻◻◻◼◼  (170)
    ◻◼◻◼◻◼◼◼◻◻  (171)
    ◻◼◻◼◻◼◼◻◼◻  (172)
    ◻◼◻◼◻◼◼◻◻◼  (173)
    ◻◼◻◼◻◼◻◼◼◻  (174)
    ◻◼◻◼◻◼◻◼◻◼  (175)
    ◻◼◻◼◻◼◻◻◼◼  (176)
    ◻◼◻◼◻◻◼◼◼◻  (177)
    ◻◼◻◼◻◻◼◼◻◼  (178)
    ◻◼◻◼◻◻◼◻◼◼  (179)
    ◻◼◻◼◻◻◻◼◼◼  (180)
    ◻◼◻◻◼◼◼◼◻◻  (181)
    ◻◼◻◻◼◼◼◻◼◻  (182)
    ◻◼◻◻◼◼◼◻◻◼  (183)
    ◻◼◻◻◼◼◻◼◼◻  (184)
    ◻◼◻◻◼◼◻◼◻◼  (185)
    ◻◼◻◻◼◼◻◻◼◼  (186)
    ◻◼◻◻◼◻◼◼◼◻  (187)
    ◻◼◻◻◼◻◼◼◻◼  (188)
    ◻◼◻◻◼◻◼◻◼◼  (189)
    ◻◼◻◻◼◻◻◼◼◼  (190)
    ◻◼◻◻◻◼◼◼◼◻  (191)
    ◻◼◻◻◻◼◼◼◻◼  (192)
    ◻◼◻◻◻◼◼◻◼◼  (193)
    ◻◼◻◻◻◼◻◼◼◼  (194)
    ◻◼◻◻◻◻◼◼◼◼  (195)
    ◻◻◼◼◼◼◼◻◻◻  (196)
    ◻◻◼◼◼◼◻◼◻◻  (197)
    ◻◻◼◼◼◼◻◻◼◻  (198)
    ◻◻◼◼◼◼◻◻◻◼  (199)
    ◻◻◼◼◼◻◼◼◻◻  (200)
    ◻◻◼◼◼◻◼◻◼◻  (201)
    ◻◻◼◼◼◻◼◻◻◼  (202)
    ◻◻◼◼◼◻◻◼◼◻  (203)
    ◻◻◼◼◼◻◻◼◻◼  (204)
    ◻◻◼◼◼◻◻◻◼◼  (205)
    ◻◻◼◼◻◼◼◼◻◻  (206)
    ◻◻◼◼◻◼◼◻◼◻  (207)
    ◻◻◼◼◻◼◼◻◻◼  (208)
    ◻◻◼◼◻◼◻◼◼◻  (209)
    ◻◻◼◼◻◼◻◼◻◼  (210)
    ◻◻◼◼◻◼◻◻◼◼  (211)
    ◻◻◼◼◻◻◼◼◼◻  (212)
    ◻◻◼◼◻◻◼◼◻◼  (213)
    ◻◻◼◼◻◻◼◻◼◼  (214)
    ◻◻◼◼◻◻◻◼◼◼  (215)
    ◻◻◼◻◼◼◼◼◻◻  (216)
    ◻◻◼◻◼◼◼◻◼◻  (217)
    ◻◻◼◻◼◼◼◻◻◼  (218)
    ◻◻◼◻◼◼◻◼◼◻  (219)
    ◻◻◼◻◼◼◻◼◻◼  (220)
    ◻◻◼◻◼◼◻◻◼◼  (221)
    ◻◻◼◻◼◻◼◼◼◻  (222)
    ◻◻◼◻◼◻◼◼◻◼  (223)
    ◻◻◼◻◼◻◼◻◼◼  (224)
    ◻◻◼◻◼◻◻◼◼◼  (225)
    ◻◻◼◻◻◼◼◼◼◻  (226)
    ◻◻◼◻◻◼◼◼◻◼  (227)
    ◻◻◼◻◻◼◼◻◼◼  (228)
    ◻◻◼◻◻◼◻◼◼◼  (229)
    ◻◻◼◻◻◻◼◼◼◼  (230)
    ◻◻◻◼◼◼◼◼◻◻  (231)
    ◻◻◻◼◼◼◼◻◼◻  (232)
    ◻◻◻◼◼◼◼◻◻◼  (233)
    ◻◻◻◼◼◼◻◼◼◻  (234)
    ◻◻◻◼◼◼◻◼◻◼  (235)
    ◻◻◻◼◼◼◻◻◼◼  (236)
    ◻◻◻◼◼◻◼◼◼◻  (237)
    ◻◻◻◼◼◻◼◼◻◼  (238)
    ◻◻◻◼◼◻◼◻◼◼  (239)
    ◻◻◻◼◼◻◻◼◼◼  (240)
    ◻◻◻◼◻◼◼◼◼◻  (241)
    ◻◻◻◼◻◼◼◼◻◼  (242)
    ◻◻◻◼◻◼◼◻◼◼  (243)
    ◻◻◻◼◻◼◻◼◼◼  (244)
    ◻◻◻◼◻◻◼◼◼◼  (245)
    ◻◻◻◻◼◼◼◼◼◻  (246)
    ◻◻◻◻◼◼◼◼◻◼  (247)
    ◻◻◻◻◼◼◼◻◼◼  (248)
    ◻◻◻◻◼◼◻◼◼◼  (249)
    ◻◻◻◻◼◻◼◼◼◼  (250)
    ◻◻◻◻◻◼◼◼◼◼  (251)
  

  (Finishes in 26 ms on an old laptop.)

---

Logic

Basic steps:

• Make an indices array of length m, init with first combination. the initial one is a combination,
• in loop,
  • increase last index (aka. m-1) till n-1, each increase will get a combination,
  • when last index become n-1, in loop,
    • increase the one before;
    • if the 2 are connected, shift current & previous to left by 1, and continue, each increase will get a combination,
    • otherwise, move the connected suffixes right after the one that is not connected, after the move, will get a combination,

End of loop:

• After increase the previous index, if its index is 0, and is the highest possible value (aka. n-m), then done;

Special cases:

• if m = 1, no need to increase previous index, that will cause out of index (-1);
• if m = n, only need return the initial combination;

---

Tips

• I figured out how to do it by inspect the first graph in: https://www.baeldung.com/cs/generate-k-combinations#comparison which is from “The Art of Computer Programming”, volume 4A (2011).
• Compare to another recursion version I wrote, the code is more complex, but quicker, especially for large input.

Jolynjolynn