問題
互いにnums をnums から
返す順は
- 各部
分集合の 中の 数は、 numsに出てくる 順のまま並べます - 部分集合どうしの
順は、 numsの前の 数から 「入れない」 「入れる」の 順に 決めていく 再帰の 順です。 たとえば nums = [1, 2]なら[[], [2], [1], [1, 2]]になります numsの長さは 0 以上 10 以下で、 同じ値は 2 回出てきません
入力と出力の例
例 1
入力
nums = [4, 7]出力
[[], [7], [4], [4, 7]]例 2
3 つに
入力
nums = [5, 1, 9]出力
[[], [9], [1], [1, 9],
[5], [5, 9], [5, 1],
[5, 1, 9]]例 3
空の
入力
nums = []出力
[[]]面接での聞かれ方
面接では、
- 「重ならない
数の 配列が あります。 部分集合を 全部返してください」 - 書き終えた
あとに 「部分 集合は いくつできますか？」 「計算量は どうなりますか？」と 続けて 聞かれます - 「同じ
値が 入っていたら どうしますか？」と、 問題文に 無い 場合を 聞かれる こともあります
返す順を
まず
段 1
まずは[4, 7] なら、
段 2
このi のi + 1 の
段 3
このwalk(i) はi からpicked に
ここから解答です。先に自分で書いてから読むと、考え方が残ります。
解答
Python
Python
def all_subsets(nums):
result = []
picked = []
def walk(i):
if i == len(nums):
snap = picked[:]
result.append(snap)
return
walk(i + 1)
picked.append(nums[i])
walk(i + 1)
picked.pop()
walk(0)
return resultJavaScript
JavaScript
function allSubsets(nums) {
const result = [];
const picked = [];
function walk(i) {
if (i === nums.length) {
result.push([...picked]);
return;
}
walk(i + 1);
picked.push(nums[i]);
walk(i + 1);
picked.pop();
}
walk(0);
return result;
}walk(i + 1) をpop でpicked が
計算量
- 時間は O(n × 2ⁿ) です。
部分 集合は 2ⁿ 個 あり、 それぞれ最大 n 個の 数を写します - 使う
記憶は、 答えを 除くと O(n) です。 再帰の 深さと pickedの長さが、 どちらも 最大 n です - 答え
その ものが 2ⁿ 個の 組なので、 これより 速い 書き方は ありません。 n が 10 なら 1024 個です
よく
- 写さずに
答えへ入れる。 result.append(picked)と書くと、 全部が 同じ 1 本の 並びを 指します。 最後に pickedが空に 戻るので、 答えは 空の 組ばかりになります - 外し忘れる。
picked.pop()を書き忘れると、 入れた 数が 次の 分かれ道まで 残り、 組が崩れます - 呼ぶ順を
逆にする。 「入れる」を 先に 呼ぶと、 部分 集合は 全部 そろっても 順が 問題文と 変わります。 決めた 順に 合わせて呼びます
面接での
書き始める
「数ごとに、
入れるか 入れないかの 2 通りが あるので、 部分 集合は 全部で 2 の n 乗個です。 前の 数から 順に 2 つに 分ける 再帰で 書きます。 入れない方を 先に たどるので、 空の 組が 最初に 出ます。」
書き終えたら、
「例 1 の
[4, 7]でたどります。 4 を 入れない 道で、 7 を 入れないと 空の 組、 入れると [7]です。戻って 4 を 入れた 道で、 同じように [4]と[4, 7]が出ます。 答えに 入れる ときは 写しを 取っているので、 あとで pickedを変えても 答えは 崩れません。」