問題
引っ越しのnums をtrue、false を
- どの
荷物も、 どちらか 一方の 組に 必ず 入れます。 荷物を 割る ことは できません - 片方の
組が 空に なっても 構いません (ただし重さは 1 以上 なので、 空の 組と 同じ 重さには なりません) numsの長さは 1 以上 200 以下、 重さは どれも 1 以上 100 以下の整数です
入力と出力の例
例 1
合計は 12 です。
入力
nums = [3, 1, 4, 2, 2]出力
true例 2
合計は 12 で
入力
nums = [2, 3, 7]出力
false例 3
合計の
入力
nums = [1, 5]出力
false面接での聞かれ方
面接では、
- 「正の
整数の 配列を、 和が 等しい 2 つの 組に 分けられるか 判定してください」 - 2 次元の
表を 書いた あとに、 「記憶を 1 次元に できますか？」 「その とき、 表を どちらの 向きに 埋めますか？ なぜですか？」と 聞かれます。 向きの 理由を 言えるかが、 シニアとして 見られる ところです - 「重さの
合計が もっと 大きかったら？」と、 表の 大きさの 限界を 聞かれる こともあります
2 組に
アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。
まず
段 1
片方のhalf ちょうどに
段 2
前から i 個のcan[i][s] とcan[i-1][s]、can[i-1][s-x] です。
段 3
行 i はcan をhalf からcan[s] をcan[s-x] は s よりcan[s-x] がtrue を
解答
Python
Python
def can_split(nums):
total = sum(nums)
if total % 2:
return False
half = total // 2
can = [False] * (half + 1)
can[0] = True
for x in nums:
s = half
while s >= x:
if can[s - x]:
can[s] = True
s -= 1
return can[half]JavaScript
JavaScript
function canSplit(nums) {
let total = 0;
for (const x of nums) {
total += x;
}
if (total % 2 !== 0) {
return false;
}
const half = total / 2;
const can = Array(half + 1)
.fill(false);
can[0] = true;
for (const x of nums) {
let s = half;
while (s >= x) {
if (can[s - x]) {
can[s] = true;
}
s--;
}
}
return can[half];
}Go
Go
func canSplit(nums []int) bool {
total := 0
for _, x := range nums {
total += x
}
if total%2 != 0 {
return false
}
half := total / 2
can := make([]bool, half+1)
can[0] = true
for _, x := range nums {
for s := half; s >= x; s-- {
if can[s-x] {
can[s] = true
}
}
}
return can[half]
}can[s] を false にcan[0] は
計算量
- 時間は O(n × half) です (half は
合計の 半分)。 荷物ごとに 表を 1 回なめます。 200 個で 重さが どれも 100 なら、 合計の 半分は 1 万で、 200 万回ほどです - 使う
記憶は O(half) です。 表 canの長さが half + 1 です - 2 次元の
表は 時間が 同じで、 記憶が O(n × half) です。 全部の 組を 試す 書き方は O(2ⁿ) です - 計算量は
重さの 合計の 大きさに 比例します。 重さが 10 億まであるような 問題では 表が 作れないので、 その 場合は 別の 方法を 考えると 言えるように しておきます
よく
- 1 次元の
表を 前から埋める。 同じ 荷物を 何回でも 使う 数え方 (何個でも 入れてよい ナップサック) に なります。 例 3 の [1, 5]でtrueを返したら、 この 間違いです - 合計が
奇数の 場合を 先に 返さない。 合計 11 の 半分を 切り捨てて 5 で 探すと、 5 が 作れた ときに trueを返してしまいます - 大きい順に
欲張って詰める。 重い 荷物から 順に、 その とき軽い ほうの 組へ 入れていく 書き方は 外れます。 [3, 3, 2, 2, 2]は 3 と 3 で 6、2 と 2 と 2 で 6 に 分けられますが、 欲張りでは 3、 2、 2 と 3、 2 に なり 7 と 5 になります - 半分を
超える 荷物を 見落とす。 1 つの 荷物が 半分より 重ければ、 その 時点で 無理です。 表の 書き方では s >= xの範囲が 空に なって 自然に 飛ばされますが、 自分で 書いた 近道で 表の 外を 読まないようにします
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「片方の
組が 合計の ちょうど 半分に なれば 分けられるので、 合計が 奇数なら 無理、 偶数なら 半分 ちょうどの 選び方が あるかを 調べます。 各荷物を 入れるか 入れないかの 0-1 ナップサックです。 表は 1 次元に して、 重さを 半分から 小さい 方へ回します。 後ろから 回すと、 読む欄は まだ前の 荷物までの 値なので、 同じ 荷物を 2 回使いません。 時間は O(n × 半分)、 記憶は O(半分) です。」
書き終えたら、
「例 1 の
[3, 1, 4, 2, 2]でたどります。 半分は 6 なので、 重さ 0 から 6 までの 表を 使います。 3 を 入れると 0 と 3 が 作れ、 1 で 1 と 4 が 足されます。 4 では 5 が 足され、 7 と 8 は 表の 外なので 見ません。 次の 2 で、 作れていた 4 に 2 を 足した 6 が 作れるので、 trueを返します。」