具有特定整数的数组的所有可能子集的最大 XOR

Question

给定一个包含 N 个整数的数组 P = [P1, P2, ..., PN] 和一个返回集合 M 中存在的所有整数的 XOR 的函数 F(M)。如果 M 为空，则 F(M) = 0.

任务是在 P 的所有可能子集 M 上找到表达式 N XOR F(M) 的最大可能值

。

形式上，找到 max(N XOR F(M)) 的值，其中 M 是 P 的子集。

Example: 

Sample Input:
N = 4
P = [1, 2, 3]
Numofintegers = 3

Sample Output :
7

Constraints :
Pi <= 1000
Number of integers <= 1000
N <= 1000

需要一个优化的解决方案，最好是在 Python 中

我使用这种方法来解决这个问题，但是复杂性太差了 - O(2 ^ N) with brute force

from itertools import combinations
def find_max_xor(N,P):
    # find the maximum XOR value
    comb = []

    for i in range(len(P) + 1):
        comb += [list(j) for j in combinations([1,2,3], i)]

    arr = []
    for i in comb:
        if len(i):
            res = 0
            for l in range(len(i)):
                res ^= i[l]
            arr.append(N ^ res)
    return max(arr)

n = 4
p = [1,2,3]
# numIntegers = 3
result = find_max_xor(n,p)
print("result : ", result)

Answer 1

简单的，在最坏的情况下最多需要 ~0.1 秒：

def find_max_xor(N, P):
    xors = {N}
    for p in P:
        xors |= {xor ^ p for xor in xors}
    return max(xors)

基准