https://www.acwing.com/problem/content/description/1700/

好像是阿里的面试题，双向dfs

cpp
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 34;

int n, m;
int w[N];

void dfs(int u, int k, int s, vector<int> &way) //当前位置，终点位置，和模上m，储存方案的数组
{
    if (u == k) way.push_back(s);
    else
    {
        dfs(u + 1, k, s, way);                  //选择第u个数
        dfs(u + 1, k, (s + w[u]) % m, way);     //不选第u个数
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> w[i];

    vector<int> A, B;
    dfs(0, n / 2, 0, A);                    //双向DFS
    dfs(n / 2, n, 0, B);

    sort(A.begin(), A.end());               //前后方案排序
    sort(B.begin(), B.end());

    int res = (A.back() + B.back()) % m;    //两段中末尾方案和最接近且小于2 * m
    for (int i = 0, j = B.size() - 1; i < A.size(); i ++ )  //双指针
    {
        while (j >= 0 && A[i] + B[j] >= m) j -- ;           //遍历找出最接近且小于m的和
        if (j >= 0) res = max(res, (A[i] + B[j]) % m);
    }

    cout << res << endl;

    return 0;
}