バックトラックで同じ値を含む並びから重ならない部分集合を全部集める

同じ値が何度か出てくる整数の並びから、選び方の違う部分集合を、同じ物を 2 回入れずに全部集めます。並べ替えてから「同じ段で同じ値を 2 回選ばない」と決めて重なりを防ぐ練習です。

海外で定番の問題リスト 4 本には入っていません

問題

お店の棚に、値段の書いた品物が並んでいます。値段の並び nums を受け取ります。同じ値段の品物が何個かあることがあります。品物をいくつか選んだときの値段の組 (1 つも選ばない空の組も含む) を全部集めて、並びにして返す関数を書いてください。

値段の組が同じ物は 1 回だけ入れます。たとえば nums = [3, 3] で 1 つ目の 3 だけ選んだ組と 2 つ目の 3 だけ選んだ組は、どちらも [3] で同じ組です
組の中の値段は、小さい順に並べます
組どうしの順は辞書の順です。前の値段から比べ、小さい方を先にします。片方がもう片方の頭と同じなら、短い方を先にします。たとえば []、[1]、[1, 2]、[2] の順です
nums の長さは 0 以上 10 以下、値段はどれも 1 以上 100 以下の整数です

入力と出力の例

例 1

5 が 2 個あります。5 を 1 個選ぶ組は、どちらの 5 を選んでも [5] の 1 つだけです。

nums = [5, 2, 5]

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

例 2

値段が全部違うと、2 の 3 乗で 8 組です。

nums = [3, 1, 2]

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

例 3

同じ値段が 3 個なら、選ぶ数が 0 から 3 個の 4 組だけです。

nums = [4, 4, 4]

[[], [4], [4, 4], [4, 4, 4]]

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「重複を含む配列から、重複しない部分集合を全部返してください」
「集合 (set) に入れて重なりを消す書き方」を出すと、「それだと、作ってから捨てる分が無駄になりませんか？作る前に防げますか？」と聞かれます
重複の無い版 (部分集合を全部) を解いたあとに、続けて出されることが多い問題です

組の中の順と、組どうしの順を最初に確かめておくと、答えが 1 つに決まり、例と比べやすくなります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

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

再帰は、同じ形の小さい問題に分けて自分を呼ぶ書き方です。木の深さや、全部の組み合わせを数える問題で使います。

まず考える手順

段 1

重複が無いときと同じように全部の選び方を作り、同じ組を集合で消す書き方がまず浮かびます。動きますが、同じ値段が多いほど作ってから捨てる組が増えます。[4, 4, 4] では 8 通り作って 4 組を残します。

段 2

まず nums を小さい順に並べ替えます。同じ値段が隣り合うので、重なりが見つけやすくなります。そのうえで、「組に次に足す品物を、いま見ている位置から後ろの中から 1 つ選ぶ」再帰にします。選ぶたびに、ここまでの組を答えに足します。後ろからしか選ばないので組の中は小さい順になり、前の値段から先に試すので組どうしは辞書の順に並びます。

段 3

重なりが出るのは、同じ段 (組の何個目を決める所) で同じ値段を 2 回選ぶときです。例 1 を並べ替えた [2, 5, 5] の頭の段で、1 つ目の 5 を選ぶのも 2 つ目の 5 を選ぶのも同じ [5] から始まります。そこで、段ごとに「この段で最後に選んだ値段」を覚えておき、それと同じ値段は飛ばします。並べ替えてあるので、これは「1 つ前と同じ値段は飛ばす」と同じです。段の最初の 1 つは飛ばしません。そうしないと [5, 5] が作れなくなります。

段 4

ここまでの組は 1 本の並びに足したり外したりして使い回し、答えに入れるときだけ写します。写さずに入れると、あとで外したときに答えの中身まで変わってしまいます。

解答

Python

def subsets_with_dups(nums):
    a = sorted(nums)
    n = len(a)
    out = []
    path = []

    def walk(s):
        out.append(path[:])
        # この段で最後に選んだ値
        prev = None
        for i in range(s, n):
            x = a[i]
            if x == prev:
                continue
            prev = x
            path.append(x)
            walk(i + 1)
            path.pop()

    walk(0)
    return out

JavaScript

function subsetsWithDups(nums) {
  const a = [...nums];
  a.sort((p, q) => p - q);
  const out = [];
  walk(a, 0, [], out);
  return out;
}

function walk(a, s, path, out) {
  out.push([...path]);
  // この段で最後に選んだ値
  let prev = null;
  const n = a.length;
  for (let i = s; i < n; i++) {
    const x = a[i];
    if (x === prev) {
      continue;
    }
    prev = x;
    path.push(x);
    walk(a, i + 1, path, out);
    path.pop();
  }
}

Go

import "sort"

func subsetsWithDups(
	nums []int,
) [][]int {
	a := []int{}
	a = append(a, nums...)
	sort.Ints(a)
	n := len(a)
	out := [][]int{}
	path := []int{}
	var walk func(s int)
	walk = func(s int) {
		p := []int{}
		p = append(p, path...)
		out = append(out, p)
		// この段で最後に選んだ値
		prev := 0
		for i := s; i < n; i++ {
			x := a[i]
			if x == prev {
				continue
			}
			prev = x
			path = append(path, x)
			walk(i + 1)
			path = path[:len(path)-1]
		}
	}
	walk(0)
	return out
}

JavaScript の sort は、比べる関数を渡さないと数を文字として並べ、[10, 9] が [10, 9] のままになります。数の並べ替えには (p, q) => p - q を渡します。Go の prev の始めを 0 にしているのは、値段が 1 以上で、どの値段とも同じにならないためです。

計算量

時間は O(2^n × n) です。組は 2^n 個までで、1 つを写すのに n までかかります。並べ替えの O(n log n) はこれに含まれます
使う記憶は、答えを除くと O(n) です。再帰の深さと、ここまでの組の長さが n までです

よくある間違い

並べ替えずに、隣と同じなら飛ばす。同じ値段が離れていると、飛ばす判定が効きません。[5, 2, 5] のままだと [5] が 2 回入ります
「最後に選んだ値」を段をまたいで持つ。 1 つの変数を全部の段で使い回すと、深い段で 2 つ目の 5 を足す所でも飛ばしてしまい、[5, 5] が作れません。覚えておく値は、段 (再帰の 1 回) ごとに用意します
ここまでの組を写さずに答えに入れる。答えの中の組が全部同じ並びを指し、最後には空の組ばかりになります
集合で重なりを消してから並べ替える。正しい答えにはなりますが、作ってから捨てる分が無駄で、面接では作る前に防ぐ書き方を求められます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def subsets_with_dups(nums: list[int]) -> list[list[int]]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(subsets_with_dups([5, 2, 5]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します