回答編集履歴
3
詳細ログ出力バージョン追記
test
CHANGED
|
@@ -373,3 +373,129 @@
|
|
|
373
373
|
return [c + l for l in combinationSum(candidates, target - c[0])] + combinationSum(candidates[1:], target)
|
|
374
374
|
|
|
375
375
|
```
|
|
376
|
+
|
|
377
|
+
---
|
|
378
|
+
|
|
379
|
+
念のため、上記ソースの詳細ログ出力バージョンを載せておきます。
|
|
380
|
+
|
|
381
|
+
呼び出しが深くなるごとにインデントを増やしているので、多少は追いやすいはずです。
|
|
382
|
+
|
|
383
|
+
```python
|
|
384
|
+
|
|
385
|
+
def debug(depth, msg):
|
|
386
|
+
|
|
387
|
+
print(' ' * depth + msg)
|
|
388
|
+
|
|
389
|
+
|
|
390
|
+
|
|
391
|
+
def combinationSum(candidates, target, depth = 0):
|
|
392
|
+
|
|
393
|
+
debug(depth, f"def combinationSum({candidates}, {target}):")
|
|
394
|
+
|
|
395
|
+
if target == 0:
|
|
396
|
+
|
|
397
|
+
debug(depth, f"return [[]]")
|
|
398
|
+
|
|
399
|
+
return [[]]
|
|
400
|
+
|
|
401
|
+
elif target < 0 or not candidates:
|
|
402
|
+
|
|
403
|
+
debug(depth, f"return []")
|
|
404
|
+
|
|
405
|
+
return []
|
|
406
|
+
|
|
407
|
+
else:
|
|
408
|
+
|
|
409
|
+
debug(depth, f"c = {candidates}[:1]")
|
|
410
|
+
|
|
411
|
+
c = candidates[:1]
|
|
412
|
+
|
|
413
|
+
debug(depth, f"=> c = {c}")
|
|
414
|
+
|
|
415
|
+
debug(depth, f"ret1 = combinationSum({candidates}, {target} - {c}[0])")
|
|
416
|
+
|
|
417
|
+
ret1 = combinationSum(candidates, target - c[0], depth + 1)
|
|
418
|
+
|
|
419
|
+
debug(depth, f"=> ret1 = {ret1}")
|
|
420
|
+
|
|
421
|
+
debug(depth, f"ret2 = [{c} + l for l in {ret1}]")
|
|
422
|
+
|
|
423
|
+
ret2 = [c + l for l in ret1]
|
|
424
|
+
|
|
425
|
+
debug(depth, f"=> ret2 = {ret2}")
|
|
426
|
+
|
|
427
|
+
debug(depth, f"ret3 = combinationSum({candidates}[1:], {target})")
|
|
428
|
+
|
|
429
|
+
ret3 = combinationSum(candidates[1:], target, depth + 1)
|
|
430
|
+
|
|
431
|
+
debug(depth, f"=> ret3 = {ret3}")
|
|
432
|
+
|
|
433
|
+
debug(depth, f"return {ret2} + {ret3}")
|
|
434
|
+
|
|
435
|
+
return ret2 + ret3
|
|
436
|
+
|
|
437
|
+
|
|
438
|
+
|
|
439
|
+
print(combinationSum([1], 2))
|
|
440
|
+
|
|
441
|
+
```
|
|
442
|
+
|
|
443
|
+
出力例
|
|
444
|
+
|
|
445
|
+
```text
|
|
446
|
+
|
|
447
|
+
def combinationSum([1], 2):
|
|
448
|
+
|
|
449
|
+
c = [1][:1]
|
|
450
|
+
|
|
451
|
+
=> c = [1]
|
|
452
|
+
|
|
453
|
+
ret1 = combinationSum([1], 2 - [1][0])
|
|
454
|
+
|
|
455
|
+
def combinationSum([1], 1):
|
|
456
|
+
|
|
457
|
+
c = [1][:1]
|
|
458
|
+
|
|
459
|
+
=> c = [1]
|
|
460
|
+
|
|
461
|
+
ret1 = combinationSum([1], 1 - [1][0])
|
|
462
|
+
|
|
463
|
+
def combinationSum([1], 0):
|
|
464
|
+
|
|
465
|
+
return [[]]
|
|
466
|
+
|
|
467
|
+
=> ret1 = [[]]
|
|
468
|
+
|
|
469
|
+
ret2 = [[1] + l for l in [[]]]
|
|
470
|
+
|
|
471
|
+
=> ret2 = [[1]]
|
|
472
|
+
|
|
473
|
+
ret3 = combinationSum([1][1:], 1)
|
|
474
|
+
|
|
475
|
+
def combinationSum([], 1):
|
|
476
|
+
|
|
477
|
+
return []
|
|
478
|
+
|
|
479
|
+
=> ret3 = []
|
|
480
|
+
|
|
481
|
+
return [[1]] + []
|
|
482
|
+
|
|
483
|
+
=> ret1 = [[1]]
|
|
484
|
+
|
|
485
|
+
ret2 = [[1] + l for l in [[1]]]
|
|
486
|
+
|
|
487
|
+
=> ret2 = [[1, 1]]
|
|
488
|
+
|
|
489
|
+
ret3 = combinationSum([1][1:], 2)
|
|
490
|
+
|
|
491
|
+
def combinationSum([], 2):
|
|
492
|
+
|
|
493
|
+
return []
|
|
494
|
+
|
|
495
|
+
=> ret3 = []
|
|
496
|
+
|
|
497
|
+
return [[1, 1]] + []
|
|
498
|
+
|
|
499
|
+
[[1, 1]]
|
|
500
|
+
|
|
501
|
+
```
|
2
自作ソース改善
test
CHANGED
|
@@ -362,12 +362,14 @@
|
|
|
362
362
|
|
|
363
363
|
return [[]]
|
|
364
364
|
|
|
365
|
-
elif target < 0 or candidates
|
|
365
|
+
elif target < 0 or not candidates:
|
|
366
366
|
|
|
367
367
|
return []
|
|
368
368
|
|
|
369
369
|
else:
|
|
370
370
|
|
|
371
|
+
c = candidates[:1]
|
|
372
|
+
|
|
371
|
-
return [
|
|
373
|
+
return [c + l for l in combinationSum(candidates, target - c[0])] + combinationSum(candidates[1:], target)
|
|
372
|
-
|
|
374
|
+
|
|
373
|
-
```
|
|
375
|
+
```
|
1
余談追加
test
CHANGED
|
@@ -316,4 +316,58 @@
|
|
|
316
316
|
|
|
317
317
|
```
|
|
318
318
|
|
|
319
|
+
`target`と等しくなった時点で以降の処理が不要になることを利用すれば、もう少し1)のソースに近くなります。
|
|
320
|
+
|
|
321
|
+
```python
|
|
322
|
+
|
|
323
|
+
def combinationSum(candidates, target):
|
|
324
|
+
|
|
325
|
+
prev_tmps = [[]]
|
|
326
|
+
|
|
327
|
+
output = []
|
|
328
|
+
|
|
329
|
+
for c in candidates:
|
|
330
|
+
|
|
331
|
+
tmps = []
|
|
332
|
+
|
|
333
|
+
for tmp in prev_tmps:
|
|
334
|
+
|
|
335
|
+
while target > sum(tmp):
|
|
336
|
+
|
|
337
|
+
tmps.append(tmp.copy())
|
|
338
|
+
|
|
339
|
+
tmp.append(c)
|
|
340
|
+
|
|
341
|
+
if sum(tmp) == target:
|
|
342
|
+
|
|
343
|
+
output.append(tmp)
|
|
344
|
+
|
|
345
|
+
prev_tmps = tmps
|
|
346
|
+
|
|
347
|
+
return output
|
|
348
|
+
|
|
349
|
+
```
|
|
350
|
+
|
|
319
351
|
2)のソースについては、`dfs(i, cur, total+candidates[i])`が現在の数字の使用回数を増やす方向、`dfs(i+1, cur, total)`が次の数字の処理に移行する方向と考えれば、理解できるのではないでしょうか。
|
|
352
|
+
|
|
353
|
+
|
|
354
|
+
|
|
355
|
+
余談ですが、私ならこう書く、というソースを載せておきます。
|
|
356
|
+
|
|
357
|
+
```python
|
|
358
|
+
|
|
359
|
+
def combinationSum(candidates, target):
|
|
360
|
+
|
|
361
|
+
if target == 0:
|
|
362
|
+
|
|
363
|
+
return [[]]
|
|
364
|
+
|
|
365
|
+
elif target < 0 or candidates == []:
|
|
366
|
+
|
|
367
|
+
return []
|
|
368
|
+
|
|
369
|
+
else:
|
|
370
|
+
|
|
371
|
+
return [[candidates[0]] + l for l in combinationSum(candidates, target - candidates[0])] + combinationSum(candidates[1:], target)
|
|
372
|
+
|
|
373
|
+
```
|