回答編集履歴
3
詳細ログ出力バージョン追記
answer
CHANGED
|
@@ -185,4 +185,67 @@
|
|
|
185
185
|
else:
|
|
186
186
|
c = candidates[:1]
|
|
187
187
|
return [c + l for l in combinationSum(candidates, target - c[0])] + combinationSum(candidates[1:], target)
|
|
188
|
+
```
|
|
189
|
+
---
|
|
190
|
+
念のため、上記ソースの詳細ログ出力バージョンを載せておきます。
|
|
191
|
+
呼び出しが深くなるごとにインデントを増やしているので、多少は追いやすいはずです。
|
|
192
|
+
```python
|
|
193
|
+
def debug(depth, msg):
|
|
194
|
+
print(' ' * depth + msg)
|
|
195
|
+
|
|
196
|
+
def combinationSum(candidates, target, depth = 0):
|
|
197
|
+
debug(depth, f"def combinationSum({candidates}, {target}):")
|
|
198
|
+
if target == 0:
|
|
199
|
+
debug(depth, f"return [[]]")
|
|
200
|
+
return [[]]
|
|
201
|
+
elif target < 0 or not candidates:
|
|
202
|
+
debug(depth, f"return []")
|
|
203
|
+
return []
|
|
204
|
+
else:
|
|
205
|
+
debug(depth, f"c = {candidates}[:1]")
|
|
206
|
+
c = candidates[:1]
|
|
207
|
+
debug(depth, f"=> c = {c}")
|
|
208
|
+
debug(depth, f"ret1 = combinationSum({candidates}, {target} - {c}[0])")
|
|
209
|
+
ret1 = combinationSum(candidates, target - c[0], depth + 1)
|
|
210
|
+
debug(depth, f"=> ret1 = {ret1}")
|
|
211
|
+
debug(depth, f"ret2 = [{c} + l for l in {ret1}]")
|
|
212
|
+
ret2 = [c + l for l in ret1]
|
|
213
|
+
debug(depth, f"=> ret2 = {ret2}")
|
|
214
|
+
debug(depth, f"ret3 = combinationSum({candidates}[1:], {target})")
|
|
215
|
+
ret3 = combinationSum(candidates[1:], target, depth + 1)
|
|
216
|
+
debug(depth, f"=> ret3 = {ret3}")
|
|
217
|
+
debug(depth, f"return {ret2} + {ret3}")
|
|
218
|
+
return ret2 + ret3
|
|
219
|
+
|
|
220
|
+
print(combinationSum([1], 2))
|
|
221
|
+
```
|
|
222
|
+
出力例
|
|
223
|
+
```text
|
|
224
|
+
def combinationSum([1], 2):
|
|
225
|
+
c = [1][:1]
|
|
226
|
+
=> c = [1]
|
|
227
|
+
ret1 = combinationSum([1], 2 - [1][0])
|
|
228
|
+
def combinationSum([1], 1):
|
|
229
|
+
c = [1][:1]
|
|
230
|
+
=> c = [1]
|
|
231
|
+
ret1 = combinationSum([1], 1 - [1][0])
|
|
232
|
+
def combinationSum([1], 0):
|
|
233
|
+
return [[]]
|
|
234
|
+
=> ret1 = [[]]
|
|
235
|
+
ret2 = [[1] + l for l in [[]]]
|
|
236
|
+
=> ret2 = [[1]]
|
|
237
|
+
ret3 = combinationSum([1][1:], 1)
|
|
238
|
+
def combinationSum([], 1):
|
|
239
|
+
return []
|
|
240
|
+
=> ret3 = []
|
|
241
|
+
return [[1]] + []
|
|
242
|
+
=> ret1 = [[1]]
|
|
243
|
+
ret2 = [[1] + l for l in [[1]]]
|
|
244
|
+
=> ret2 = [[1, 1]]
|
|
245
|
+
ret3 = combinationSum([1][1:], 2)
|
|
246
|
+
def combinationSum([], 2):
|
|
247
|
+
return []
|
|
248
|
+
=> ret3 = []
|
|
249
|
+
return [[1, 1]] + []
|
|
250
|
+
[[1, 1]]
|
|
188
251
|
```
|
2
自作ソース改善
answer
CHANGED
|
@@ -180,8 +180,9 @@
|
|
|
180
180
|
def combinationSum(candidates, target):
|
|
181
181
|
if target == 0:
|
|
182
182
|
return [[]]
|
|
183
|
-
elif target < 0 or
|
|
183
|
+
elif target < 0 or not candidates:
|
|
184
184
|
return []
|
|
185
185
|
else:
|
|
186
|
+
c = candidates[:1]
|
|
186
|
-
return [
|
|
187
|
+
return [c + l for l in combinationSum(candidates, target - c[0])] + combinationSum(candidates[1:], target)
|
|
187
188
|
```
|
1
余談追加
answer
CHANGED
|
@@ -157,4 +157,31 @@
|
|
|
157
157
|
output.append(tmp)
|
|
158
158
|
return output
|
|
159
159
|
```
|
|
160
|
+
`target`と等しくなった時点で以降の処理が不要になることを利用すれば、もう少し1)のソースに近くなります。
|
|
161
|
+
```python
|
|
162
|
+
def combinationSum(candidates, target):
|
|
163
|
+
prev_tmps = [[]]
|
|
164
|
+
output = []
|
|
165
|
+
for c in candidates:
|
|
166
|
+
tmps = []
|
|
167
|
+
for tmp in prev_tmps:
|
|
168
|
+
while target > sum(tmp):
|
|
169
|
+
tmps.append(tmp.copy())
|
|
170
|
+
tmp.append(c)
|
|
171
|
+
if sum(tmp) == target:
|
|
172
|
+
output.append(tmp)
|
|
173
|
+
prev_tmps = tmps
|
|
174
|
+
return output
|
|
175
|
+
```
|
|
160
|
-
2)のソースについては、`dfs(i, cur, total+candidates[i])`が現在の数字の使用回数を増やす方向、`dfs(i+1, cur, total)`が次の数字の処理に移行する方向と考えれば、理解できるのではないでしょうか。
|
|
176
|
+
2)のソースについては、`dfs(i, cur, total+candidates[i])`が現在の数字の使用回数を増やす方向、`dfs(i+1, cur, total)`が次の数字の処理に移行する方向と考えれば、理解できるのではないでしょうか。
|
|
177
|
+
|
|
178
|
+
余談ですが、私ならこう書く、というソースを載せておきます。
|
|
179
|
+
```python
|
|
180
|
+
def combinationSum(candidates, target):
|
|
181
|
+
if target == 0:
|
|
182
|
+
return [[]]
|
|
183
|
+
elif target < 0 or candidates == []:
|
|
184
|
+
return []
|
|
185
|
+
else:
|
|
186
|
+
return [[candidates[0]] + l for l in combinationSum(candidates, target - candidates[0])] + combinationSum(candidates[1:], target)
|
|
187
|
+
```
|