問題はこちら
難易度はmedium
問題概要
異なる整数のcandidateの配列と、対象となる整数の target が与えられたとき、選ばれた数値の合計が target となる候補のすべてのユニークな組み合わせのリストを返します。組み合わせはどのような順番で返してもよい。
候補から同じ数字が選ばれる回数は無制限である。
テストケースは、与えられた入力に対して、合計がターゲットになるユニークな組合せの数が150組合せ未満になるように生成される。
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
答え
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(start, path, target):
if target == 0:
result.append(path)
return
for i in range(start, len(candidates)):
if candidates[i] <= target:
backtrack(i, path + [candidates[i]], target - candidates[i])
result = []
candidates.sort()
backtrack(0, [], target)
return result
backtrack()を再帰で呼び出してます。最初にcandidate.sort()で小さい順にしています。
start: candidate[]の指数になります。もちろん呼び出されるごとに、後ろへ行きます。つまり、candidate[start]から後ろ半分を渡している、と考えても良いかもしれません。
path: 答え候補となります。int[].呼び出される際、candidate[i]を一つ追加。
target: 足して目標となる数字です。呼び出される時target-candidate[i]されているので、その分小さくなります。最終的に０になったところで、その時のpathが答えに追加されます。
イメージとしては、candidate[]とtargetをどんどん小さくして、簡単な問題にしていく感じです。
例１を使います。
最初[2,3,6,7]と７が渡された時、for文の中で
backtrack([2,3,6,7], [2], 5)
backtrack([3,6,7], [3], 4)
backtrack([6,7], [6], 1)
backtrack([7], [7], 0)
が呼ばれます。
backtrack([2,3,6,7], [2], 5)はさらに
backtrack([2,3,6,7], [2,2], 3)
backtrack([3,6,7], [2,3], 2)
が呼ばれます。target 5 が candidate[i] 6より小さくなるとそれ以降のfor文では呼ばれません。
コード改良
今回はなし