UVa: 624 - CD

#include <iostream>

#define GB(m, x) ((m) &  (1<<(x)))
#define SB(m, x) ((m) | (1<<(x)))
#define CB(m, x) ((m) &= ~(1<<(x)))

using namespace std;

int bitSol;
int n;
int a[21];
int maxDur;
int minDif;

void solve(int bitMask, int i, int p)
{
    if(p > maxDur)
        return;

    if(p <= maxDur && p > minDif)
        minDif = p, bitSol = bitMask;

    if(i < n)
    {
        solve(SB(bitMask, i), i+1, p+a[i]);
        solve(bitMask, i+1, p);
    }
}


int main()
{
    while(cin >> maxDur)
    {
        cin >> n;
        for(int i=0; i<n; i++)
            cin >> a[i];
        minDif = 0;
        bitSol = 0;
        solve(0, 0, 0);

        for(int i=0; i<n; i++)
        {
            if(GB(bitSol, i))
            {
                cout << a[i] << " ";
            }
        }
        cout << "sum:" << minDif << endl;
    }
    return 0;
}