LeetCode解説　一日一問　39. Combination Sum

LeetCodeって？
問題
回答
コード
結果

LeetCodeって？

Just a moment...

LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。

2022年12月現在2,000問を超える問題が登録されています。

各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。

正誤判定は自動で行われます。

使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。

私はPython3で解いています。

Pythonではじめるアルゴリズム入門伝統的なアルゴリズムで学ぶ定石と計算量 [ 増井敏克 ]

問題

Combination Sum II - LeetCode

Can you solve this real interview question? Combination Sum II - Given a collection of candidate numbers (candidates) and a target number (target), find all uni...

タイトル：40. Combination Sum II

難易度：Medium

内容：

1 から 50 の自然数が入ったリスト candidates と 1 から 30 の自然数 target が与えられる。
candidates の値を足し合わせて target の値を作成できるすべての組み合わせを返す。
ただし、一度使用したcandidates の値を再度使用してはいけない。

例：

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6], [1,2,5], [1,7], [2,6]]

Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2], [5]]

回答

前回の問題と似ています。

変更点は、

candidates に重複した値がある場合がある
一度使用した candidates の値を再度使用してはいけない

です。

前回のコードを多少いじくるだけで解けます。

コード

前回と違う部分のみ注釈を入れています。

class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        combinations = []
        
        def comb(cand, target, ans):
            pre_cand = -1 # 追加
            for i, c in enumerate(cand):
                if c == pre_cand:
                    # candidatesに重複した値が含まれていて、同じ組み合わせを出力してしまうので追加
                    continue
                pre_cand = c # 追加
                cur_ans = ans.copy()
                cur_ans.append(c)
                cur_target = target - c
                cur_cand = [cand[j] for j in range(len(cand)) if cand[j] <= cur_target and j > i]
                  # 一度使用した値は使えないので、cur_candの抽出条件を j >= i から j > i に変更

                if cur_target == 0:
                    combinations.append(cur_ans)
                    continue

                elif len(cur_cand) < 1:
                    continue

                comb(cur_cand, cur_target, cur_ans)
            return combinations
        
        cand = [i for i in candidates if i <= target]
        cand = sorted(candidates)
        return comb(cand, target, [])

コードはgithubにも保管しています。