提供一个非递归的做法，基本思路是一样的，就是利用位表示是否选了，有点像状态压缩dp，但是写位运算比较有快感，而且运行时间大概是y总代码一半。
代码如下：

#include <iostream>
#include <cstring>
#include <queue>
#include <string>
#include <algorithm>
#include <unordered_set>
#include <set>
using namespace std;
typedef long long ll; 
typedef pair<int, string> pis;
const int N = 17;
const ll st = (1<<N);
ll leftPart[st];
ll rightPart[st];
int arr[N*2];
int n, m, l, r;

ll lowbit(ll x) {
    return x & (-x);
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i ++) {
        cin >> arr[i];
    }
    l = n / 2;
    r = n - l;
    ll leftst = (1 << l);
    ll rightst = (1 << r);
    for(int i = 0; i < l; i ++) {
        leftPart[(1 << i)] = arr[i] % m;
    }
    for(int i = 0; i < leftst; i ++) {
        leftPart[i] = (leftPart[i - lowbit(i)] + leftPart[lowbit(i)]) % m;
    }
    for(int i = 0; i < r; i ++) {
        rightPart[(1 << i)] = arr[l+i] % m;
    }
    for(int i = 0; i < rightst; i ++) {
        rightPart[i] = (rightPart[i-lowbit(i)] + rightPart[lowbit(i)]) % m;
    }
    sort(leftPart, leftPart + leftst);
    sort(rightPart, rightPart + rightst);
    int res = (leftPart[leftst-1] + rightPart[rightst-1]) % m;
    for(int i = 0, j = rightst - 1; i < leftst; i ++) {
        while(j > 0 && leftPart[i] + rightPart[j] >= m) {
            j --;
        }
        res = max(res, (int)(leftPart[i] + rightPart[j]));
    }
    cout <<res << endl;
    return 0;
}