Combinatorics

Subarrays (for Arrays) - (n * (n + 1) / 2)

A subarray is a contiguous segment of an array. If you have an array arr, a subarray is any slice arr[i:j] where 0 ≤ i ≤ j ≤ arr.length.

function findSubarrays(arr) {
  let result = [];

  function backtrack(start, path) {
    if (path.length > 0) {
      result.push([...path]);
    }
    for (let i = start; i < arr.length; i++) {
      path.push(arr[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(0, []);
  return result;
}

let arr = [1, 2, 3];
console.log(findSubarrays(arr));
// Output: [[1], [1, 2], [1, 2, 3], [2], [2, 3], [3]]

Substrings (for Strings) - (n * (n + 1) / 2)

A substring is a contiguous segment of a string. If you have a string str, a substring is any slice str[i:j] where 0 ≤ i ≤ j ≤ str.length.

function findSubstrings(str) {
  let result = [];

  function backtrack(start, path) {
    if (path.length > 0) {
      result.push(path);
    }
    for (let i = start; i < str.length; i++) {
      backtrack(i + 1, path + str[i]);
    }
  }

  backtrack(0, "");
  return result;
}

let str = "abc";
console.log(findSubstrings(str));
// Output: ["a", "ab", "abc", "b", "bc", "c"]

Subsequences (for Arrays) - 2^n

A subsequence is any sequence derived from an array or string by deleting some or no elements without changing the order of the remaining elements.

function findSubsequences(arr) {
  let result = [];

  function backtrack(start, path) {
    result.push([...path]);
    for (let i = start; i < arr.length; i++) {
      path.push(arr[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(0, []);
  return result;
}

let arr = [1, 2, 3];
console.log(findSubsequences(arr));
// Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Subsequences (for Strings) - 2^n

function findSubsequences(str) {
  let result = [];

  function backtrack(start, path) {
    result.push(path);
    for (let i = start; i < str.length; i++) {
      backtrack(i + 1, path + str[i]);
    }
  }

  backtrack(0, "");
  return result;
}

let str = "abc";
console.log(findSubsequences(str));
// Output: ["", "a", "ab", "abc", "ac", "b", "bc", "c"]

Permutations (for Arrays) - n!

A permutation is a rearrangement of the elements of an array or string into a different sequence.

function findPermutations(arr) {
  let results = [];

  function permute(current, remaining) {
    if (remaining.length === 0) {
      results.push(current);
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      let next = remaining.slice();
      next.splice(i, 1);
      permute(current.concat(remaining[i]), next);
    }
  }

  permute([], arr);
  return results;
}

let arr = [1, 2, 3];
console.log(findPermutations(arr));
// Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Permutations (for Strings)- n!

function findPermutations(arr) {
  let result = [];

  function backtrack(path, used) {
    if (path.length === arr.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < arr.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(arr[i]);
      backtrack(path, used);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([], Array(arr.length).fill(false));
  return result;
}

let arr = [1, 2, 3];
console.log(findPermutations(arr));
// Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Combinations (for Arrays)

function findCombinations(n, k) {
  let result = [];

  function backtrack(start, path) {
    if (path.length === k) {
      result.push([...path]);
      return;
    }

    for (let i = start; i <= n; i++) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(1, []);
  return result;
}

console.log(findCombinations(4, 2));
// Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]