【LeetCode】40. Combination Sum II 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：Python, backtracking
2. 解答2:
メモ・参考・感想

問題

原文

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

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

1
2
3
4
5
6
7
8

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

Example 2:

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

1
2
3
4
5
6

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

Constraints:

1 <= candidates.length <= 100

1 <= candidates[i] <= 50

1 <= target <= 30

内容

候補数字の集合であるcandidatesと目標数字であるtargetが与えられます。

合計値がtargetと一致するcandidates内各要素の固有な組み合わせを全て見つけてください。

candidates内の各数字は組み合わせの中で一度だけ使用できます。

注意：解答は重複する組み合わせを含んではいけません。

※正しくない可能性があります。

解答

解答1：Python, backtracking

"""
backtrackingは全ての解の候補から、条件に該当するものだけを取り出す手法
深さ優先探索を使って再帰的に処理を行って実装することが一般的
"""

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        #各変数を初期化
        answer = [] #この問題の解答
        index = 0    #後のdfs(backtracking)で使用するインデックス
        subset = []  #合計値がtargetになる要素の集合。subsetの各要素はcandidates内にある要素の一部。subset自体はanswerの一要素になる。
        sum_of_subset = 0
        
        #candidatesを昇順ソート　※後の重複判定が簡単になる
        candidates.sort()
        #dfsを呼び出す
        self.dfs(index,candidates,subset, sum_of_subset, target, answer)
        #answerを返す
        return answer

    #dfs関数を使ってbacktrackingを行う
    def dfs(self, index, candidates, subset, sum_of_subset, target, answer):
        #subsetの合計がtargetと一致する場合
        if sum_of_subset == target:
            #解答に候補を加える
            answer.append(subset)
            return
        #subsetの合計がtargetよりも大きくなった場合
        if sum_of_subset > target:
            #何もせずにreturn
            return
        #candidatesを一巡して走査する。
        for i in range(index, len(candidates)):
            #candidatesは最初に昇順ソートされているので、重複の判定はi-1番目とi番目の値の比較で良い
            #candidatesのi番目の要素がi-1番目の要素と同じ場合は何もしないことで、同じsubsetが作られることを予防
            #candidates=[1,1,2],target=3の場合、この操作がないとanswer=[[1,2],[1,2]]になる
            if i > index and candidates[i]==candidates[i-1]:
                continue
            #再帰的に呼び出す    
            #i+1でindexを一つ増やすことでcandidatesのi+1番目以降の要素だけを使って同じ処理をする
            #リストであるsubsetにはi番目の要素をリストとして加える
            #subsetの合計値にもi番目の要素を加える
            #candidates,target,answerはそのまま
            self.dfs(i+1, candidates, subset+[candidates[i]], sum_of_subset+candidates[i], target, answer)

"""

backtrackingは全ての解の候補から、条件に該当するものだけを取り出す手法

深さ優先探索を使って再帰的に処理を行って実装することが一般的

"""

class Solution:

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

#各変数を初期化

answer = [] #この問題の解答

index = 0 #後のdfs(backtracking)で使用するインデックス

subset = [] #合計値がtargetになる要素の集合。subsetの各要素はcandidates内にある要素の一部。subset自体はanswerの一要素になる。

sum_of_subset = 0

#candidatesを昇順ソート　※後の重複判定が簡単になる

candidates.sort()

#dfsを呼び出す

self.dfs(index,candidates,subset, sum_of_subset, target, answer)

#answerを返す

return answer

#dfs関数を使ってbacktrackingを行う

def dfs(self, index, candidates, subset, sum_of_subset, target, answer):

#subsetの合計がtargetと一致する場合

if sum_of_subset == target:

#解答に候補を加える

answer.append(subset)

return

#subsetの合計がtargetよりも大きくなった場合

if sum_of_subset > target:

#何もせずにreturn

return

#candidatesを一巡して走査する。

for i in range(index, len(candidates)):

#candidatesは最初に昇順ソートされているので、重複の判定はi-1番目とi番目の値の比較で良い

#candidatesのi番目の要素がi-1番目の要素と同じ場合は何もしないことで、同じsubsetが作られることを予防

#candidates=[1,1,2],target=3の場合、この操作がないとanswer=[[1,2],[1,2]]になる

if i > index and candidates[i]==candidates[i-1]:

continue

#再帰的に呼び出す

#i+1でindexを一つ増やすことでcandidatesのi+1番目以降の要素だけを使って同じ処理をする

#リストであるsubsetにはi番目の要素をリストとして加える

#subsetの合計値にもi番目の要素を加える

#candidates,target,answerはそのまま

self.dfs(i+1, candidates, subset+[candidates[i]], sum_of_subset+candidates[i], target, answer)

バックトラッキングは全ての解の候補から、条件に一致するものだけを集めることで解を求める手法。

解答2:

メモ・参考・感想

前：200. Number of Islands

次：17. Letter Combinations of a Phone Number

LeetCode 解答・解説記事一覧