O(2ⁿ) — Exponential Time

// Fibonacci แบบ naive — O(2ⁿ)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // แตก 2 กิ่งทุกครั้ง
}

console.log(fib(5));  // 5
console.log(fib(10)); // 55
console.log(fib(20)); // 6765 (แต่เริ่มช้าเห็นได้ชัด)

// fib(4) เรียก fib(3) และ fib(2)
// fib(3) เรียก fib(2) และ fib(1)
// fib(2) เรียก fib(1) และ fib(0)
// = 9 ครั้งการเรียก (1 + 2 + 4 + 2)

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// n=4  → 9 ครั้ง
// n=5  → 15 ครั้ง
// n=10 → 177 ครั้ง
// n=20 → 21,891 ครั้ง — โตเร็วมาก!

function generateBinaryStrings(n) {
  const result = [];

  function backtrack(current) {
    if (current.length === n) {
      result.push(current);
      return;
    }
    backtrack(current + "0");
    backtrack(current + "1");
  }

  backtrack("");
  return result;
}

console.log(generateBinaryStrings(3));
// ["000","001","010","011","100","101","110","111"] — 8 = 2³
console.log(generateBinaryStrings(4).length); // 16 = 2⁴

// array [a, b, c] มี subsets ทั้งหมด 8 = 2³ แบบ:
// []  [a]  [b]  [c]  [a,b]  [a,c]  [b,c]  [a,b,c]
//
// n = 0 → 1
// n = 1 → 2
// n = 2 → 4
// n = 3 → 8
// n = 10 → 1024
//
// การสร้างทุก subset ต้องใช้ O(2ⁿ) เพราะต้องสร้างทุกชุด

function countSubsets(arr) {
  return Math.pow(2, arr.length); // 2ⁿ
}

console.log(countSubsets(["a", "b", "c"])); // 8

// ❌ คูณ 2 ทุกรอบใน loop — O(log n) ไม่ใช่ O(2ⁿ)
let i = 1;
while (i < n) {
  i *= 2;  // i = 1, 2, 4, 8, ...
}

// ❌ Recursion กิ่งเดียว — O(n) ไม่ใช่ O(2ⁿ)
function sum(n) {
  if (n <= 0) return 0;
  return n + sum(n - 1); // เรียกตัวเองครั้งเดียว
}

// ❌ Fibonacci with memoization — O(n) ไม่ใช่ O(2ⁿ)
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}