Phân tích của một số nguyên dương n là một cách viết n dưới dạng tổng các số nguyên dương. Hai tổng chỉ khác nhau về thứ tự các số hạng được coi là cùng một phân tích.
Ví dụ, 4 có thể được phân tích theo năm cách khác nhau:
4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1
Chúng ta cần viết một hàm JavaScript nhận vào một số nguyên dương làm đối số duy nhất. Hàm nên tìm và trả về tất cả các cách phân tích số nguyên đó.
Ví dụ
Dưới đây là mã nguồn:
const findPartitions = (num = 1) => { const arr = Array(num + 1).fill(null).map(() => { return Array(num + 1).fill(null); }); for (let j = 1; j <= num; j += 1) { arr[0][j] = 0; } for (let i = 0; i <= num; i += 1) { arr[i][0] = 1; } for (let i = 1; i <= num; i += 1) { for (let j = 1; j <= num; j += 1) { if (i > j) { arr[i][j] = arr[i - 1][j]; } else { const exclusive = arr[i - 1][j]; const inclusive = arr[i][j - i]; arr[i][j] = exclusive + inclusive; } } } return arr[num][num]; }; console.log(findPartitions(4));Kết quả
Đầu ra trên console:
5
Lưu ý: Hàm này chỉ trả về số lượng phân tích (partition number p(n)), không trả về danh sách các phân tích cụ thể. Để lấy danh sách, cần thuật toán backtracking.