624 - CD, uva

I didn't use recursion here I just used binary numbers which generate all possible combinations

lets say you have 5 objects we'll denote a combination by a binary number

so for a set {A,B,C,D,E} and binary number N where the ith bit says if the ith element has been taken or not

so {A,B,C,D,E}

00000 = {} the null set

10000 = {A}

01000 = {B}

11000 = {A,B}

etc...

If we keep counting from zero to 2^n (Excluding 2^n) we'll generate all possible combinations (power set)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define db(a) cout << #a << " = " << a << endl
#define foreach(it, l) for ( typeof(l.begin()) it = l.begin(); it != l.end(); it++) 
#define dbl(i, a) cout << "[" << i << "]" << " = "<< a << ", "; 
#define listar(lista) for(int i = 0; i < lista.size(); i++) { dbl(i, lista[i]);} cout << endl;
using namespace std;
int main() {
 int sum, cur, max, arreglo[20], index, n, tracks;
 while (scanf("%d", &n) != EOF) {
  scanf("%d", &tracks);
  sum = cur = index = 0;
  max = 1 << tracks;
  for (int i = 0; i < tracks; i++) 
   scanf("%d", arreglo + i);
   
  for (int i = 0; i < max; i++) {
   cur = 0;
   for (int j = 0; j < tracks; j++) {
    if ((1 << j) & i) {
     cur += arreglo[j];
    }
   }
   if (cur >= sum && cur <= n) 
    sum = cur, index = i;
  }
  for (int i = 0;i < tracks; i++) {
   if (1 << i & index) {
    printf("%d ", arreglo[i]);
   }
  }
  printf("sum:%d\n", sum);
 }
 return 0;
}