当前位置: 面试刷题>> 整数拆分 (经典算法题500道)


题目描述补充

题目:整数拆分

给定一个正整数n,将其拆分成至少两个正整数的和,并求出所有可能的拆分方式。每种拆分方式中的数字顺序不同视为不同的拆分方式。例如,当n = 4时,可能的拆分方式有:[4](注意这里虽然只包含一个数字,但题目要求至少两个数的拆分,所以此情况通常不计入结果,除非有特殊说明)、[1, 3][2, 2][1, 1, 2][1, 2, 1][3, 1][2, 1, 1][1, 1, 1, 1](但通常我们不考虑包含全部为1的拆分,因为它会产生大量重复的排列,除非题目明确要求)。

为了简化问题,我们假设:

  1. 拆分结果中至少包含两个数字。
  2. 拆分结果不考虑顺序(即[1, 2][2, 1]视为同一种拆分方式,但在这个问题中,由于我们要求列出所有可能的拆分并包含顺序不同的拆分,所以实际上会列出所有可能的组合)。

注意:基于题目描述,我们这里假设要列出所有可能的拆分方式,包括那些包含1的拆分,但会忽略全为1的拆分(如果n较大时,全为1的拆分会非常多,且没有实际意义)。

PHP 示例代码

function integerBreak($n) {
    $result = [];
    backtrack($n, 1, [], $result);
    return $result;
}

function backtrack($n, $start, $current, &$result) {
    if ($n == 0) {
        if (count($current) > 1) { // 确保拆分结果至少有两个数
            $result[] = $current;
        }
        return;
    }
    
    for ($i = $start; $i <= $n; $i++) {
        $current[] = $i;
        backtrack($n - $i, $i, $current, $result);
        array_pop($current);
    }
}

// 测试
$n = 4;
$result = integerBreak($n);
foreach ($result as $partition) {
    echo implode(', ', $partition) . PHP_EOL;
}

注意:上述PHP代码实际上会列出所有可能的拆分,包括重复的拆分(如[1, 2, 1][1, 1, 2]被视为不同)。如果要去除这种重复,需要对算法进行进一步调整,比如使用集合或进行排序比较。

Python 示例代码

def integerBreak(n):
    def backtrack(start, path, res):
        if sum(path) == n:
            if len(path) > 1:  # 确保拆分结果至少有两个数
                res.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i, path, res)
            path.pop()

    res = []
    backtrack(1, [], res)
    return res

# 测试
n = 4
result = integerBreak(n)
for partition in result:
    print(', '.join(map(str, partition)))

JavaScript 示例代码

function integerBreak(n) {
    const result = [];

    function backtrack(start, current) {
        if (current.reduce((a, b) => a + b, 0) === n) {
            if (current.length > 1) { // 确保拆分结果至少有两个数
                result.push([...current]);
            }
            return;
        }

        for (let i = start; i <= n; i++) {
            current.push(i);
            backtrack(i, current);
            current.pop();
        }
    }

    backtrack(1, []);
    return result;
}

// 测试
const n = 4;
const result = integerBreak(n);
result.forEach(partition => console.log(partition.join(', ')));

码小课网站中有更多关于算法和数据结构的内容,包括整数拆分问题的深入解析和优化方法,欢迎大家前往学习。

推荐面试题