Quay lui (backtracking) cho bài tập leo cầu thang trong JavaScript

Giả sử cần leo một cầu thang có n bậc, và bạn quyết định nhảy các bậc để tập thể dục. Mỗi lần nhảy tối đa k bậc, với k chỉ bằng 1 hoặc 2 bất kể số bậc cầu thang.

Yêu cầu: Trả về tất cả các chuỗi nhảy có thể thực hiện để leo lên cầu thang, đã sắp xếp.

Ví dụ: n = 4, k = 2 cho kết quả:

[[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2]]

Ví dụ (đếm số cách leo)

Mã dưới đây dùng đệ quy có nhớ (memoization) để đếm số cách leo (không liệt kê chuỗi):

const n = 4;
const climbStairs = (n) => {
  if (n === 0) return 0;
  let memory = new Map();
  let recur = (left) => {
    if (memory.has(left)) return memory.get(left);
    if (left <= 0) return 0;
    if (left === 1) return 1;
    if (left === 2) return 2;
    memory.set(left, recur(left - 2) + recur(left - 1));
    return memory.get(left);
  };
  return recur(n);
};
console.log(climbStairs(n)); // 5

Kết quả

5

Lưu ý: Hàm trên chỉ đếm số cách, không sinh ra các mảng chuỗi nhảy như yêu cầu đề bài.