当前位置： 面试刷题>> 拆分子数组 (经典算法题500道)
### 题目描述补充
题目：拆分子数组
给定一个整数数组 `nums` 和一个整数 `k`，要求将数组 `nums` 拆分成若干个非空子数组，使得每个子数组中的元素和都不超过 `k`。你需要返回所有可能的拆分方案。
**注意**：拆分后的子数组需要保持原数组的顺序。
**示例**：
输入：`nums = [1, 2, 2, 1]`, `k = 5`
输出：
```
[
[[1], [2, 2, 1]],
[[1, 2], [2, 1]],
[[1, 2, 2], [1]]
]
```
### PHP 代码示例
```php
function partitionArray($nums, $k) {
$result = [];
backtrack($nums, $k, 0, [], $result);
return $result;
}
function backtrack($nums, $k, $start, $current, &$result) {
if ($start == count($nums)) {
if (!empty($current)) {
$result[] = $current;
}
return;
}
$sum = 0;
for ($i = $start; $i < count($nums); $i++) {
$sum += $nums[$i];
if ($sum > $k) {
break;
}
$current[] = $nums[$i];
backtrack($nums, $k, $i + 1, $current, $result);
array_pop($current);
}
}
// 测试用例
$nums = [1, 2, 2, 1];
$k = 5;
$output = partitionArray($nums, $k);
print_r($output);
```
### Python 代码示例
```python
def partitionArray(nums, k):
result = []
def backtrack(start, current):
if start == len(nums):
if current:
result.append(current[:])
return
sum_so_far = 0
for i in range(start, len(nums)):
sum_so_far += nums[i]
if sum_so_far > k:
break
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
# 测试用例
nums = [1, 2, 2, 1]
k = 5
output = partitionArray(nums, k)
print(output)
```
### JavaScript 代码示例
```javascript
function partitionArray(nums, k) {
const result = [];
function backtrack(start, current) {
if (start === nums.length) {
if (current.length > 0) {
result.push([...current]);
}
return;
}
let sum = 0;
for (let i = start; i < nums.length; i++) {
sum += nums[i];
if (sum > k) {
break;
}
current.push(nums[i]);
backtrack(i + 1, current);
current.pop();
}
}
backtrack(0, []);
return result;
}
// 测试用例
const nums = [1, 2, 2, 1];
const k = 5;
const output = partitionArray(nums, k);
console.log(output);
```
**码小课**：以上示例展示了如何在不同编程语言中通过回溯算法解决拆分子数组的问题。在码小课网站上，您可以找到更多关于算法和数据结构的详细讲解和实战练习，帮助您更深入地掌握相关知识。