feat(backtracking): all combinations of k numbers out of 1...n (TheAlgorithms#148)

nebarf · web-flow · commit 5f5352daeef4 · 2023-08-29T12:30:56.000+05:30
* feat(backtracking): all combinations of k numbers out of 1...n

* refactor(backtracking): remove default of 'startCursor' param

* docs(backtracking): add docs

* refactor(backtracking): move recursive routine in closure
diff --git a/backtracking/all-combinations-of-size-k.ts b/backtracking/all-combinations-of-size-k.ts
@@ -0,0 +1,38 @@
+/**
+ * This generates an array of unique sub"sets" (represented by ascendingly sorted subarrays)
+ * of size k out of n+1 numbers from 1 to n.
+ *
+ * By using a backtracking algorithm we can incrementally build sub"sets" while dropping candidates
+ * that cannot contribute anymore to a valid solution.
+ * Steps:
+ * - From the starting number (i.e. "1") generate all combinations of k numbers.
+ * - Once we got all combinations for the given number we can discard it (“backtracks”)
+ *   and repeat the same process for the next number.
+ */
+export function generateCombinations(n: number, k: number): number[][] {
+  let combinationsAcc: number[][] = [];
+  let currentCombination: number[] = [];
+
+  function generateAllCombos(
+    n: number,
+    k: number,
+    startCursor: number
+  ): number[][] {
+    if (k === 0) {
+      if (currentCombination.length > 0) {
+        combinationsAcc.push(currentCombination.slice());
+      }
+      return combinationsAcc;
+    }
+
+    const endCursor = n - k + 2;
+    for (let i = startCursor; i < endCursor; i++) {
+      currentCombination.push(i);
+      generateAllCombos(n, k - 1, i + 1);
+      currentCombination.pop();
+    }
+    return combinationsAcc;
+  }
+
+  return generateAllCombos(n, k, 1);
+}
diff --git a/backtracking/test/all-combinations-of-size-k.test.ts b/backtracking/test/all-combinations-of-size-k.test.ts
@@ -0,0 +1,26 @@
+import { generateCombinations } from "../all-combinations-of-size-k";
+
+const cases = [
+  [
+    3,
+    2,
+    [
+      [1, 2],
+      [1, 3],
+      [2, 3],
+    ],
+  ],
+  [4, 2, [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]],
+  [0, 0, []],
+  [2, 3, []],
+] as const;
+
+describe("AllCombinationsOfSizeK", () => {
+  it.each(cases)(
+    "create all combinations given n=%p and k=%p",
+    (n, k, expectedCombos) => {
+      const combinations = generateCombinations(n, k);
+      expect(combinations).toEqual(expectedCombos);
+    }
+  );
+});
