[백준] 1208번: 부분수열의 합 2

https://www.acmicpc.net/problem/1208

initial

It is similar to the 부분수열의합 question but this time, n is increased from 20 to 40. We have solved that previous question with backtracking so if we take the same approach, time complexity is from 2^20 to 2^40 which is mega huge and will cause runtime.

googled and this is pretty clear: https://sensol2.tistory.com/80

So i didnt know how to differ. Should I use a different algorithm like idk dp? But actually i googled and we can split the given list into 2 sub lists and if we do backtracking on each sub list, it is gonna be 2^20 + 2^20 time so it is durable. We put all possible sums of subsequences in the given sublist in the respective left_dictionary (for left sublist) as key and the number of occurrences of that given sum value as value in our dictionary and same for right_dict (for right sublist).

We also need to consider an empty set where a sum value in left_dic could be equal to the question’s given desired sum value without needing to add a sum value in right_dic. So we need {0:1} in both dictionaries, which will be placed when we run the backtracking function at the start. An edge case is that if question’s given sum is 0, then this empty sets in both dictionaries are gonna be wrongly added. Like there is 0 in both dicts, which if we add those 2 we still get the desired sum of 0 so we dont want that. So when dicA’s key is 0 and dicB’s key is also 0, we dont want to add +1 to our answer so we minus 1 at the end.

solution

actually we dont need that return statement

import sys
input=sys.stdin.readline
n, s = map(int, input().split())
lst = list(map(int, input().split()))

left_dict, right_dict = {}, {}
ans = 0

def dfs(index, hola, option, _sum):
    if option == "left":
        left_dict[_sum] = left_dict.get(_sum, 0) + 1
    else:
        right_dict[_sum] = right_dict.get(_sum, 0) + 1

    if index == len(hola):
        return

    for i in range(index, len(hola)):
        _sum += hola[i]
        dfs(i + 1, hola, option, _sum)
        _sum -= hola[i]

mid = len(lst) // 2
dfs(0, lst[:mid], "left", 0)
dfs(0, lst[mid:], "right", 0)

for a in left_dict.keys():
    if s - a in right_dict.keys():
        ans += left_dict[a] * right_dict[s - a]

if s == 0:
    ans -= 1

print(ans)

using 2 pointers

i find this also good
https://c4u-rdav.tistory.com/61

complexity

as mentioned, since we are doing dfs on halved lists, the time is 2^n/2

The DFS function is called twice, once for the left and once for the right half of the list. Each call explores all possible subsets of the corresponding half, resulting in a time complexity of O(2^(n/2)), where n is the size of the input list.
The loop that iterates over the keys of left_dict has a time complexity of O(a), where a is the number of distinct sums in the left half.
Within this loop, the check if s - a in right_dict.keys(): has a time complexity of O(1) on average.
The overall time complexity is dominated by the DFS part, making it O(2^(n/2)).

Space Complexity:

The space complexity is determined by the space required for the dictionaries left_dict and right_dict. In the worst case, the space complexity for each dictionary is O(2^(n/2)), where n is the size of the input list.
The recursive depth of the DFS function is at most n/2, contributing to the call stack space.
The overall space complexity is O(2^(n/2)).