Дополнение по комбинаторике

Поиск всех подмассивов - (n * (n + 1) / 2)

Пример кода

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]]

Поиск всех подмножеств - 2^n

Пример кода

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]]

Поиск всех перестановок - n!

Пример кода

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]]