バックトラックで足すと目標になる組み合わせを全部集める｜コーディング面接問題

問題

正の整数の並び candidates と、正の整数 target を受け取ります。candidates の数を何度でも使ってよいとして、足すと target になる組み合わせを全部返す関数を書いてください。

candidates の値はどれも違います。同じ数を 2 回以上使うのはかまいません
使う数とその回数が同じなら、同じ組み合わせです。[2, 3, 3] と [3, 2, 3] は 1 回だけ返します
組み合わせの中は小さい順に並べます。組み合わせどうしは辞書の順 (先頭の数から比べ、小さいほうが先。同じなら次の数で比べる) に並べます
そういう組み合わせが無いときは、空の並び [] を返します
candidates の長さは 1 以上 30 以下、値は 2 以上 40 以下、target は 1 以上 40 以下です

入力と出力の例

例 1

入力

candidates = [3, 5, 2]
target = 8

出力

[[2, 2, 2, 2],
 [2, 3, 3],
 [3, 5]]

例 2

target そのものが並びにあれば、1 つだけの組み合わせも答えです。

入力

candidates = [6, 3, 9]
target = 9

出力

[[3, 3, 3], [3, 6], [9]]

例 3

どう足しても 7 にならないときは、空の並びです。

入力

candidates = [4, 6]
target = 7

出力

[]

面接での聞かれ方

面接では、「金額をちょうど払える硬貨の組み合わせを全部挙げてください」のような場面で出されることが多いです。

書き始めて少しすると、「[2, 3, 3] と [3, 2, 3] が両方出ていませんか？」と、重なりを指摘されます
「同じ数は 1 回しか使えないなら、どこを変えますか？」と、条件を変えた続きを聞かれます
書き終えたあとに「どこで探すのをやめていますか？」と、枝の切り方を聞かれます

「次に選ぶ数は、いま選んだ数より前には戻らない」と決めるだけで、重なりが出なくなることを言えるのが芯です。

アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。

まず考える手順

段 1

まずは素直に、「残りの額から、どれか 1 つの数を引く」を 0 になるまでくり返し、ちょうど 0 になった選び方を集める書き方を考えます。ただ、毎回すべての数から選ぶと、[2, 3, 3]、[3, 2, 3]、[3, 3, 2] のように、同じ組み合わせが並べ方の数だけ出てきます。

段 2

並べ方の違いを出さないため、candidates を小さい順に並べ替え、「次に選べるのは、いま選んだ数と同じかそれより右の数だけ」と決めます。こうすると、組み合わせは必ず小さい順に選ばれ、1 つの組み合わせは 1 通りの選び方でしか作れません。同じ数をもう一度使えるように、次の始まりは j + 1 ではなく j にします。

段 3

選ぶ、先へ進む、取り消す、の 3 つを 1 組にします。いまの選び方 path に数を足し、残りの額を減らして奥へ進み、戻ってきたら path から外します。残りが 0 になったら、path の写しを答えに足します。

段 4

小さい順に並べてあるので、残りの額より大きい数に当たったら、その先の数も全部大きすぎます。そこで繰り返しを打ち切ります。小さい数から順に選ぶので、答えは自然に辞書の順に並びます。

解答

Python

def combination_sum(
    candidates, target
):
    a = sorted(candidates)
    n = len(a)
    out = []
    path = []

    def dfs(i, left):
        if left == 0:
            out.append(path[:])
            return
        for j in range(i, n):
            if a[j] > left:
                break
            path.append(a[j])
            dfs(j, left - a[j])
            path.pop()

    dfs(0, target)
    return out

JavaScript

function combinationSum(
  candidates, target
) {
  const a = [...candidates];
  a.sort((p, q) => p - q);
  const out = [];
  dfs(a, 0, target, [], out);
  return out;
}

function dfs(
  a, i, left, path, out
) {
  if (left === 0) {
    out.push([...path]);
    return;
  }
  const n = a.length;
  for (let j = i; j < n; j++) {
    const x = a[j];
    if (x > left) {
      break;
    }
    path.push(x);
    const rest = left - x;
    dfs(a, j, rest, path, out);
    path.pop();
  }
}

Go

import "sort"

func combinationSum(
	candidates []int, target int,
) [][]int {
	a := []int{}
	a = append(a, candidates...)
	sort.Ints(a)
	n := len(a)
	out := [][]int{}
	path := []int{}
	var dfs func(i, left int)
	dfs = func(i, left int) {
		if left == 0 {
			p := []int{}
			p = append(p, path...)
			out = append(out, p)
			return
		}
		for j := i; j < n; j++ {
			if a[j] > left {
				break
			}
			path = append(path, a[j])
			dfs(j, left-a[j])
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return out
}

path は 1 本を使い回して、足しては外します。答えに入れるときだけ写しを作ります。写さずに path そのものを入れると、あとで外した分まで答えから消えてしまいます。

計算量

時間は、candidates の長さを n、奥行きの最大を d (target をいちばん小さい数で割った数。この問題では最大 20 段) とすると、最悪で O(nᵈ) ほどの枝をたどります。各段で最大 n 通りを試すからです。実際は、残りの額を超えた所で打ち切るので、ずっと少なく済みます
使う記憶は、返す答えを除くと O(d) です。path と呼び出しの深さの分です。ほかに、並べ替えた写しに O(n) を使います
答えの数そのものが多くなりうる問題なので、「答えを 1 つずつ作る手間に比べて、むだな枝をどれだけ切れるか」で速さが決まります

よくある間違い

次の始まりを毎回 0 にする。すべての数から選び直すと、[2, 3, 3] と [3, 2, 3] のように同じ組み合わせが並べ方の数だけ出ます。次は j から選びます
次の始まりを j + 1 にする。 同じ数を 2 回使えなくなり、例 1 の [2, 2, 2, 2] が出なくなります。j + 1 は「1 回ずつしか使えない」問題の書き方です
path の写しを作らずに答えへ入れる。 答えの中のどれもが同じ 1 本の path を指し、最後には全部が空の並びになります。Python は path[:]、JavaScript は [...path]、Go は新しい slice へ写します

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

バックトラックで足すと目標になる組み合わせを全部集める

問題