回答編集履歴
2
スライス演算削除
test
CHANGED
|
@@ -1,3 +1,19 @@
|
|
|
1
|
+
スライス演算削除してさらに高速化（本質は kazuma-s さんと同じです）
|
|
2
|
+
```Python
|
|
3
|
+
def comb_sum(nums, val, sz, idx=0, exist=False):
|
|
4
|
+
if exist and val == 0:
|
|
5
|
+
return True
|
|
6
|
+
if val < 0 or idx >= sz:
|
|
7
|
+
return False
|
|
8
|
+
return (comb_sum(nums, val - nums[idx], sz, idx+1, True) or
|
|
9
|
+
comb_sum(nums, val, sz, idx+1, exist))
|
|
10
|
+
|
|
11
|
+
n, s = map(int, input().split())
|
|
12
|
+
nums = [*map(int, input().split())]
|
|
13
|
+
ans = comb_sum(nums, s, len(nums))
|
|
14
|
+
print('YES' if ans else 'NO')
|
|
15
|
+
```
|
|
16
|
+
|
|
1
17
|
高速化しました。
|
|
2
18
|
```Python
|
|
3
19
|
def comb_sum(nums, val, exist=False):
|
1
高速化
test
CHANGED
|
@@ -1,3 +1,19 @@
|
|
|
1
|
+
高速化しました。
|
|
2
|
+
```Python
|
|
3
|
+
def comb_sum(nums, val, exist=False):
|
|
4
|
+
if exist and val == 0:
|
|
5
|
+
return True
|
|
6
|
+
if val < 0 or not nums:
|
|
7
|
+
return False
|
|
8
|
+
return comb_sum(nums[1:], val - nums[0], True) + comb_sum(nums[1:], val, exist)
|
|
9
|
+
|
|
10
|
+
n, s = map(int, input().split())
|
|
11
|
+
nums = [*map(int, input().split())]
|
|
12
|
+
ans = comb_sum(nums, s)
|
|
13
|
+
print('YES' if ans else 'NO')
|
|
14
|
+
```
|
|
15
|
+
|
|
16
|
+
以前のコードです。
|
|
1
17
|
```Python
|
|
2
18
|
def comb_sum(nums, val):
|
|
3
19
|
if val <= 0 or not nums:
|