JavaScript Algorithm: Generate All Combinations of Size K (Backtracking Explained)

All Combinations of Size K

📌 What is This Algorithm?

The All Combinations of Size K algorithm helps in generating all possible groups (combinations) of "k" numbers from a given range "1" to "n". Unlike permutations, the order of numbers does not matter.

💡 Example

Suppose we have "n = 4" and we want all groups of size "k = 2". The valid combinations are:

  [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]
  

🚀 How Does It Work?

This algorithm uses recursion and backtracking to explore all possible ways of selecting numbers.

• We start with an empty list.
• We add numbers one by one while ensuring the group size doesn’t exceed "k".
• If the group reaches size "k", we store it.
• Then, we remove the last number (backtrack) and try the next possibilities.

🛠️ Code Implementation

function generateCombinations(n, k) {
  let currentCombination = [];
  let allCombinations = []; // Stores all valid combinations
  let currentValue = 1;

  function findCombinations() {
    if (currentCombination.length === k) {
      // Once we reach the required size, store the combination
      allCombinations.push([...currentCombination]);
      return;
    }
    if (currentValue > n) {
      // If we exceed the available numbers, stop
      return;
    }
    currentCombination.push(currentValue++);
    findCombinations(); // Explore further
    currentCombination.pop(); // Remove last element (backtrack)
    findCombinations(); // Try the next number
    currentValue--; // Restore the previous value
  }

  findCombinations();
  return allCombinations;
}

export { generateCombinations };
  

📌 Example Usage

Let’s generate all combinations of size "2" from numbers "1" to "4":

import { generateCombinations } from './your-file.js';

console.log(generateCombinations(4, 2));

// Output:
// [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
  

⏳ Time Complexity

The total number of combinations is given by the formula: "C(n, k) = n! / (k! * (n-k)!)".

This means the complexity is roughly "O(C(n, k))", which can grow large for bigger values of "n".

📌 Where is This Used?

• Generating lottery numbers
• Finding all possible teams from a group
• Solving problems in probability and statistics
• Backtracking-based solutions in coding interviews