I was pretty surprised by my latest question for a recruitment interview. I just recently published a blog post about permutation. But the new question that I have to answer was about generating combination. Until now, I am still not sure on how to solve it. But similar, yet simpler problem is the k-combinations problem.

Given set is a collection of unique items, k-combinations is a complete list of every possible subset with k number of entries. For example, in a set of {🍇,🍎,🍌}. The k-combinations of the set with k value of 2 are: {{🍇,🍎},{🍇,🍌},{🍎,🍌}}.

Note that, ordering doesn't matter in a set. Such that the subset {🍇,🍎} is the same subset as {🍎,🍇} and the latter shouldn't be included in the list. For robustness, items listed earlier in the input list must be placed earlier in the output list as well.

The task is to define a function in that returns all k-combinations of a particular set:

Example 1:

• inputs:
  • set: {🍇,🍎,🍌}
  • k: 2
• output: {{🍇,🍎},{🍇,🍌},{🍎,🍌}}

Example 2:

• inputs:
  • set: {🍇,🍎,🍌,🍓,🥭}
  • k: 3
• output:

{
  {🍇,🍎,🍌},
  {🍇,🍎,🍓},
  {🍇,🍎,🥭},
  {🍇,🍌,🍓},
  {🍇,🍌,🥭},
  {🍇,🍓,🥭},
  {🍎,🍌,🍓},
  {🍎,🍌,🥭},
  {🍎,🍓,🥭},
  {🍌,🍓,🥭},
};

In the average office setup, this type of question is potentally easy to solve. As there are aboundant resource on the internet and the solutions are already published from multiple sources. However, when the rules are on-site, no-search-engine and no-external-library, I had to solely rely on my own intuition to complete the problem.

Unfortunately, I blank out again on the problem. After the interview, I restudied the problem. If you look closely, the type of items here don't really matter. It can be numbers, strings, or object of fruits like the problem statement. You can simply lookup k-combinations on search engines, and you will get many solutions to the same problem.

However, many online solutions again resorts to recursion, and I am not very fond of it. I need an approach that can be internalized in my brain, if I want to derive the same solution in the same setting.

I tried to search for non-recursive solution and found the iterative approach. The code is just brilliant. It is like my first time seeing bitwise operators like <<, >>=, ++n and u=u&(u-1), in the wild. I studied more about it and apparently you deduce k-combinations on sets with size N by counting the number of 1 in binary representation of numbers 2^{N}. I think it was a little bit too smart.

So, I decided to derive my own solution. I realize that you can still use insertion technique here. Here's the code that I derive at:

function kCombination(n: number, k: number): number[][] {
  let output: number[][] = [[]];
  for (let size = 1; size <= k; size++) {
    let outputNew = [];
    for (let rootIndex = 0; rootIndex < output.length; rootIndex++) {
      const root = output[rootIndex];
      for (
        let newEntry: number = root[root.length - 1] + 1 || 0;
        newEntry < n;
        newEntry++
      ) {
        const branch = root.concat(newEntry);
        outputNew.push(branch);
      }
    }
    output = outputNew;
  }
  return output;
}

If you have read my previous blog post on permutation, you will realize that they are very similar. There are 3 for loops required.

// We initialized the output with one empty root
let output: number[][] = [[]];

In permutation, the outer loop is to iterate the rest of the entries. But in k-combination, the outer loop is to iterate through the size of each subset until it reaches size of k.

// We started the insertion from the size = 1,
// such that the number of item in the subset is just 1.
for (let size = 1; size <= k; size++) {
  // The outputNew will later replace the output
  let outputNew = [];

  // MORE CODE HERE

  // Replace output with the outputNew
  output = outputNew;
}

The inner loops is where the insertion happens.

// We iterate every existing root that exist in the output.
// It starts with just one empty root.
// But the root will grow, as branches will be root in the higher size.
for (let rootIndex = 0; rootIndex < output.length; rootIndex++) {
  //It can be a for of loop here as well

  const root = output[rootIndex];

  // In the inner third loop for permutation,
  // we iterate all the possible indices for insertions.
  // But in combination, we iterate on all of the possible new entry
  // based on the last value of the current root.
  for (
    // The || here is necessary in taking care of initial empty set.
    let newEntry: number = root[root.length - 1] + 1 || 0;
    newEntry < n;
    newEntry++;
  ) {

    // We simply add the new entry at the end of the current root
    // This creates a new branch.
    const branch = root.concat(newEntry);
    outputNew.push(branch);
  }
}

Supposed that we added the following loggers and call the function:

function kCombination(n: number, k: number): number[][] {
  let output: number[][] = [[]];
  for (let size = 1; size <= k; size++) {
    let outputNew = [];
    for (let rootIndex = 0; rootIndex < output.length; rootIndex++) {
      const root = output[rootIndex];
      console.log("root: " + JSON.stringify(root)); // LOGGING

      for (
        let newEntry: number = root[root.length - 1] + 1 || 0;
        newEntry < n;
        newEntry++
      ) {
        const branch = root.concat(newEntry);
        console.log("branch: " + JSON.stringify(branch)); // LOGGING
        outputNew.push(branch);
      }
    }
    output = outputNew;
    console.log("output: " + JSON.stringify(output)); // LOGGING
  }
  return output;
}
kCombination(5, 3);

We will get the following output:

root: []
branch: [0]
branch: [1]
branch: [2]
branch: [3]
branch: [4]
output: [[0],[1],[2],[3],[4]]
root: [0]
branch: [0,1]
branch: [0,2]
branch: [0,3]
branch: [0,4]
root: [1]
branch: [1,2]
branch: [1,3]
branch: [1,4]
root: [2]
branch: [2,3]
branch: [2,4]
root: [3]
branch: [3,4]
root: [4]
output: [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
root: [0,1]
branch: [0,1,2]
branch: [0,1,3]
branch: [0,1,4]
root: [0,2]
branch: [0,2,3]
branch: [0,2,4]
root: [0,3]
branch: [0,3,4]
root: [0,4]
root: [1,2]
branch: [1,2,3]
branch: [1,2,4]
root: [1,3]
branch: [1,3,4]
root: [1,4]
root: [2,3]
branch: [2,3,4]
root: [2,4]
root: [3,4]
output: [[0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

As you can see from the log, new branches will form based on the last value found in the root. Besides, not all roots will produce new branches. The base k-combinations is all done and we can simply map the relevant items in the set this way:

function kCombinationSet<T>(set: Array<T>, k: number): T[][] {
  return kCombination(set.length, k).map((val) => val.map((val) => set[val]));
}

Logging the answer to the problems:

console.log(JSON.stringify(kCombinationSet(["🍇", "🍎", "🍌"], 2)));
// [["🍇","🍎"],["🍇","🍌"],["🍎","🍌"]]

console.log(JSON.stringify(kCombinationSet(["🍇", "🍎", "🍌", "🍓", "🥭"], 3)));
// [
//   ["🍇", "🍎", "🍌"],
//   ["🍇", "🍎", "🍓"],
//   ["🍇", "🍎", "🥭"],
//   ["🍇", "🍌", "🍓"],
//   ["🍇", "🍌", "🥭"],
//   ["🍇", "🍓", "🥭"],
//   ["🍎", "🍌", "🍓"],
//   ["🍎", "🍌", "🥭"],
//   ["🍎", "🍓", "🥭"],
//   ["🍌", "🍓", "🥭"],
// ];

As a bonus generating powerset or every possible subset of a particular set is a simple modification of the function. We added base variable that store only the latest branches. While the output variable always push the latest branches. We also grow the size until n or the size of the set.

function powerset(n: number): number[][] {
  let output: number[][] = [[]];
  let base: number[][] = [[]];
  for (let size = 1; size <= n; size++) {
    let outputNew = [];
    for (let rootIndex = 0; rootIndex < base.length; rootIndex++) {
      const root = base[rootIndex];
      for (
        let newEntry: number = root[root.length - 1] + 1 || 0;
        newEntry < n;
        newEntry++
      ) {
        const branch = root.concat(newEntry);
        outputNew.push(branch);
      }
    }
    base = outputNew;
    output.push(...outputNew);
  }
  return output;
}

function powersetSet<T>(set: Array<T>, k: number): T[][] {
  return powerset(set.length).map((val) => val.map((val) => set[val])));
}

console.log(JSON.stringify(powersetSet(["🍇", "🍎", "🍌", "🍓", "🥭"], 3)));

// [
//   [],
//   ["🍇"],
//   ["🍎"],
//   ["🍌"],
//   ["🍓"],
//   ["🥭"],
//   ["🍇", "🍎"],
//   ["🍇", "🍌"],
//   ["🍇", "🍓"],
//   ["🍇", "🥭"],
//   ["🍎", "🍌"],
//   ["🍎", "🍓"],
//   ["🍎", "🥭"],
//   ["🍌", "🍓"],
//   ["🍌", "🥭"],
//   ["🍓", "🥭"],
//   ["🍇", "🍎", "🍌"],
//   ["🍇", "🍎", "🍓"],
//   ["🍇", "🍎", "🥭"],
//   ["🍇", "🍌", "🍓"],
//   ["🍇", "🍌", "🥭"],
//   ["🍇", "🍓", "🥭"],
//   ["🍎", "🍌", "🍓"],
//   ["🍎", "🍌", "🥭"],
//   ["🍎", "🍓", "🥭"],
//   ["🍌", "🍓", "🥭"],
//   ["🍇", "🍎", "🍌", "🍓"],
//   ["🍇", "🍎", "🍌", "🥭"],
//   ["🍇", "🍎", "🍓", "🥭"],
//   ["🍇", "🍌", "🍓", "🥭"],
//   ["🍎", "🍌", "🍓", "🥭"],
//   ["🍇", "🍎", "🍌", "🍓", "🥭"],
// ];

Glad that we have done it without recursion again. Remember, recursion is never the solution. Always say no to recursion.