LeetCodeって？
LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。
2022年12月現在2,000問を超える問題が登録されています。
各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。
正誤判定は自動で行われます。
使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。
私はPython3で解いています。
Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量 [ 増井 敏克 ]
問題
タイトル：39. Combination Sum
難易度：Medium
内容：
2 から 40 の重複のない自然数が入ったリスト candidates と 1 から 40 の自然数 target が与えられる。
candidates の値を足し合わせて target の値を作成できるすべての組み合わせを返す。
なお candidates の値は重複して使用してよい。
例：
Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: ※2 + 2 + 3 = 7、7 = 7
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]
Input: candidates = [2], target = 1 Output: []
回答
再起関数を使って、全ての組み合わせを網羅する方法を考えてみます。
解法
返り値を入れるリストを初期化します。
combinations = []
候補となる値のリストを cand 、ターゲットを target 、途中の組み合わせのリストを ans として、cand を組み合わせて target の値にする関数 comb を定義します。
def comb(cand, target, ans):
cand = [2,3,6,7], target = 7 の場合を考えてみます。まだ候補はないので ans = [] です。
Ⅰ
まず、2 を使うことを考えてみます。すると 7 – 2 = 5 となるので、今度は cand を使って 5 を作ればいいことになります。
この時、6, 7 は 5 より大きいので、cand = [2, 3] にできます。
よって次は cand = [2,3], target = 5, ans = [2] として comb 関数を実行します。
Ⅱ
また 2 を使ってみます。すると 5 – 2 = 3 で、cand = [2,3], target = 3, ans = [2, 2] となります。
これらをまた引数として comb 関数を実行します。
Ⅲ
また 2 を使ってみます。すると 3 – 2 = 1 になり、cand = [2,3] だったので、成立しないことが分かります。
Ⅳ
Ⅱ に戻って今度は 3 を使ってみます。すると足して 7 になります。
なので combinations に [2, 2, 3] を追加します。
このようにしていくことで、すべての取りうる組み合わせを検証し網羅します。
コード
上記の理論をコードにします。
class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
combinations = [] # 返り値を初期化
def comb(cand, target, ans):
#cand：候補となる値のリスト
#target：ターゲットの値
#ans：途中の組み合わせ
for i in cand:
cur_ans = ans.copy() # ansをcur_ansにコピー
# .copy()を使わないとansがグローバルに書き換えられてしまう
cur_ans.append(i) # cur_ansにiを追加
cur_target = target - i # ターゲットからはiをi引く
cur_cand = [j for j in cand if j <= cur_target and j >= i]
# 候補となるのは、target以下の値と
# i以上の値（i以上を条件にしないと同じ組み合わせが２回以上出てくる）
if cur_target == 0: # ターゲットが0になれば
combinations.append(cur_ans) # 返り値に現在の答えを格納
continue # 次の組み合わせを探しに行く
elif len(cur_cand) < 1: # 候補の値が0になったら
continue # 次の組み合わせを探しに行く
comb(cur_cand, cur_target, cur_ans) # 更新された候補、ターゲットをもとにcombを再起
return combinations
cand = [i for i in candidates if i <= target]
cand = sorted(candidates)
return comb(cand, target, [])コードはgithubにも保管しています。
結果
かなりいい結果が出ました。
再起関数はやっぱり説明が難しいです。書いて慣れるしかないですね。
コメント