2012年10月11日

UVa 574 - Sum It Up


#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
using std::string;
using std::map;

int num[12], flag, n;
map<string, int> dic;

void run(int sum, int times, int *check) {
  if (!sum) {
    flag = 1;
    int i;
    string s;
    for (i = n - 1; i >= 0; i--)
      if (check[i]) {
        char temp[10];
        sprintf(temp, "%d", num[i]);
        s.append(temp);
        break;
      }
    for (i--; i >= 0; i--)
      if (check[i]) {
        char temp[10];
        sprintf(temp, "+%d", num[i]);
        s.append(temp);
      }
    if (dic[s]) return;
    else dic[s] = 1;
    puts(s.c_str());
    return;
  }
  if (sum < 0 || times == -1) return;
  check[times] = 1;
  run(sum - num[times], times - 1, check);
  check[times] = 0;
  run(sum, times - 1, check);
}

int main() {
  int t;
  while (scanf("%d%d", &t, &n) && t || n) {
    dic.erase(dic.begin(), dic.end());
    for (int i = 0; i < n; i++)
      scanf("%d", &num[i]);
    flag = 0;
    std::sort(num, num + n);
    int check[12] = {};
    printf("Sums of %d:\n", t);
    run(t, n - 1, check);
    if (!flag) puts("NONE");
  }
  return 0;
}

沒有留言:

張貼留言