python - 计算分区相等子集和问题的时间复杂度

Question

def group(arr):
    s1 = []
    s2 = arr

    _sum = sum(arr)
    if _sum & 1:
        return None, None
    n, memo = len(arr), {0: True}
    arr.sort(reverse=True)

    def dfs(i, new_sum):
        if new_sum not in memo:
            memo[new_sum] = False
            if new_sum > 0 or new_sum < 0:
                for j in range(i, n):
                    if dfs(j + 1, new_sum - arr[j]):
                        memo[new_sum] = True
                        s1.append(arr[j])
                        s2.remove(arr[j])
                        break
        return memo[new_sum]

    k = dfs(0, _sum >> 1)  # call recursive func
    if not k:
        return None, None
    return s1, s2

s = [2, 8, 5, 5]
group(s)

上面的函数结合了 DFS 的使用和我从https://leetcode.com/problems/partition-equal-subset-sum/discuss/276278/Python-DP-and-(DFS%2BMemo)采用的 Memoization并具有稍作修改以解决以下挑战：

1. 描述

S 是一组至少 2 个无特定顺序的整数。问题是是否有办法将 S 分成 2 个集合（S1 和 S2），使得 S1 中的整数之和等于 S2 中的整数之和。S 中的元素必须始终在 S1 或 S2 中，但不能同时在两者中。在某些情况下，同一个 S 可能有多种解决方案。

2. 挑战

编写一个名为 group 的函数，它接受 S，并返回 (None, None)（如果没有解决方案）或解决方案 (S1, S2)。group 返回 2 个列表。（Python 中的函数可以返回 2 个值 - 请参见此处的示例）。如果有多个解决方案，则只需返回其中一个。

3. 问题

我在推导函数的时间复杂度时遇到了麻烦，因为我不擅长递归......谁能解释/指导我完成计算上述时间复杂度 O(n) 的过程？

我非常感谢您的帮助、时间和精力。非常感谢。

标签： pythonrecursiontime-complexitydepth-first-searchsubset-sum