Phân hoạch của số nguyên dương n là 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ủa các tổng và được coi là cùng một phân vùng.
Ví dụ:4 có thể được phân vùng theo năm cách riêng biệt -
4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1
Chúng tôi được yêu cầu viết một hàm JavaScript lấy một số nguyên dương làm đối số duy nhất. Hàm sẽ tìm và trả về tất cả các cách có thể để phân vùng số nguyên đó.
Ví dụ
Sau đây là mã -
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)); Đầu ra
Sau đây là kết quả trên bảng điều khiển -
5