题目描述补充

题目：拆分子数组

给定一个整数数组 nums 和一个整数 k，要求将数组 nums 拆分成若干个非空子数组，使得每个子数组中的元素和都不超过 k。你需要返回所有可能的拆分方案。

注意：拆分后的子数组需要保持原数组的顺序。

示例：

输入：nums = [1, 2, 2, 1], k = 5

输出：

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

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 代码示例

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 代码示例

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);

码小课：以上示例展示了如何在不同编程语言中通过回溯算法解决拆分子数组的问题。在码小课网站上，您可以找到更多关于算法和数据结构的详细讲解和实战练习，帮助您更深入地掌握相关知识。