問題
どれもnums をnums の
- 返す順は
次の 決まりに 従います。 並べ方の 1 つ目の 数は、 numsで前に ある 数を 先に 選びます。 1 つ目が 同じ 並べ方 どうしは、 2 つ目の 数を、 残りの 数の うち numsで前に ある 方から 選びます。 3 つ目からも同じです - たとえば
nums = [2, 1]なら、[2, 1]が先、 [1, 2]が後です。 値の 大小ではなく、 numsの中の 位置で 順が 決まります numsの長さは 1 以上 6 以下、 値は どれも 絶対値が 10 以下です
入力と出力の例
例 1
1 つ目に 4、
入力
nums = [4, 7, 1]出力
[[4, 7, 1], [4, 1, 7],
[7, 4, 1], [7, 1, 4],
[1, 4, 7], [1, 7, 4]]例 2
2 つなら、
入力
nums = [0, -2]出力
[[0, -2], [-2, 0]]例 3
1 つだけなら、
入力
nums = [5]出力
[[5]]面接での聞かれ方
面接では、
- 「重複の
無い 配列の、 全部の 順列を 返してください」 - 書き終えた
あとに 「答えは いくつに なりますか」 「計算量は？」と、 答えの 数その ものが 大きいことに 気づいているかを 聞かれます - 「値に
重複が あったら どうしますか」と、 続きの 問題を 聞かれる こともあります
返す順を
アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。
まず
段 1
並べ方を
段 2
席を 1 つpath と、used をnums のpath の
段 3
1 つのpath からused の
解答
Python
Python
def permute(nums):
n = len(nums)
used = [False] * n
path, out = [], []
def walk():
if len(path) == n:
out.append(path[:])
return
for i in range(n):
if used[i]:
continue
used[i] = True
path.append(nums[i])
walk()
path.pop()
used[i] = False
walk()
return outJavaScript
JavaScript
function permute(nums) {
const n = nums.length;
const used = new Set();
const path = [];
const out = [];
const walk = () => {
if (path.length === n) {
out.push([...path]);
return;
}
nums.forEach((x, i) => {
if (used.has(i)) return;
used.add(i);
path.push(x);
walk();
path.pop();
used.delete(i);
});
};
walk();
return out;
}Go
Go
func permute(
nums []int,
) [][]int {
n := len(nums)
used := make([]bool, n)
path := []int{}
out := [][]int{}
var walk func()
walk = func() {
if len(path) == n {
cp := append(
[]int{}, path...,
)
out = append(out, cp)
return
}
for i, x := range nums {
if used[i] {
continue
}
used[i] = true
path = append(path, x)
walk()
path = path[:len(path)-1]
used[i] = false
}
}
walk()
return out
}答えにpath のpath そのpop した
計算量
- 時間は O(n × n!) です。
並べ方が n! 通り あり、 それぞれを 写すのに O(n) かかります。 途中の 枝分かれで 使った 印を 調べる 手間も、 同じ 大きさに 収まります - 答えを
除いて 使う 記憶は O(n) です。 pathとusedと、再帰の n 段分です。 答え その ものは n! 個の 並びで、 O(n × n!) の 大きさになります - 答えを
全部返す以上、 n! より 速くは できません。 面接では 「出力の 大きさが 下限です」と 言えると十分です
よく
- 写さずに足す。 Python で
out.append(path)と書くと、 答えの 中身が 全部同じ 1 つの 並びを 指し、 最後には 空の 並びが n! 個並びます - 戻し忘れ。
used[i] = False(JavaScript ならused.delete(i)) を書かないと、 最初の 1 通りを 作った あとは、 どの 数も 使用済みのままに なり、 答えが 1 つしか出ません - 入れ替えで
作って 順がずれる。 nums[k]とnums[i]を入れ替えて 作る 書き方も 正しい 並べ方を 全部作りますが、 例 1 では 5 番目と 6 番目が [1, 7, 4]、[1, 4, 7]の順に なり、 決めた 順と 合いません。 順が 決まっている 問題では、 作り方が 順を 決める ことに 気をつけます - Go で path を
そのまま足す。 append(out, path)は同じ裏の 配列を 共有するので、 あとの 書き換えが 前の 答えに 入り込みます。 append([]int{}, path...)で写します - 重複の
ある 入力に使う。 値が 同じ数が 2 つあると、 同じ 並べ方が 2 回出ます。 重複を 許す問題では、 並べ替えたうえで 「同じ値の 前の 数を まだ 使っていなければ 飛ばす」 決まりを足します
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「席を
前から 埋めていく 再帰で 書きます。 使った 数に 印を 付けて、 使っていない 数を 元の 並びの 前から 試し、 全部の 席が 埋まったら 写しを 答えに 足します。 試し終えたら 印を 外して 戻すバックトラックです。 並べ方が n! 通り あって、 それぞれ写すのに n かかるので、 時間は O(n × n!) です。 出力の 大きさが それなので、 これより 速くは できません。」
書き終えたら、
「例 1 の
[4, 7, 1]でたどります。 1 つ目に 4 を 選ぶと、 残りは 7 と 1 なので、 [4, 7, 1]、[4, 1, 7]の順に できます。 4 の 印を 外して、 次に 7 を 選ぶと [7, 4, 1]、[7, 1, 4]、最後に 1 を 選ぶと [1, 4, 7]、[1, 7, 4]です。合わせて 3! の 6 通りです。」