# Best travel 5 kyu

[Best travel](https://www.codewars.com/kata/55e7280b40e1c4a06d0000aa)
5 kyu

## Solution

/**
*** Author: R-CO
*** E-Mail: [e-mail]
*** Date: 2020-08-11
**/
#include <algorithm>
#include <cstdlib>
#include <iostream>
using std::cout;
using std::endl;
#include <vector>

struct TestCaseStruct {
  struct Input {
    int t;
    int k;
    std::vector<int> ls;
  } input;
  int expected_output;
};

class BestTravel {
 public:
  static int chooseBestSum(int t, int k, std::vector<int>& ls);

 private:
  static void FindRecursively(int t, int k, std::vector<int>& ls,
                              std::vector<int>& used, int sum, int& best_sum) {
    if (k == 0) {
      if (sum > best_sum) {
        best_sum = sum;
      }
      return;
    }

    for (int i = static_cast<int>(ls.size()) - 1; i >= 0; --i) {
      if (used[i] > 0) {
        continue;
      }

      if (ls[i] > t) {
        continue;
      }

      t -= ls[i];
      sum += ls[i];
      used[i] = 1;
      --k;
      FindRecursively(t, k, ls, used, sum, best_sum);
      t += ls[i];
      sum -= ls[i];
      used[i] = 0;
      ++k;
    }
  }
};

int BestTravel::chooseBestSum(int t, int k, std::vector<int>& ls) {
  if (t < 0 || k <= 0 || static_cast<size_t>(k) > ls.size()) {
    return -1;
  }

  std::sort(ls.begin(), ls.end());
  int sum = 0;
  for (int i = 0; i < k; ++i) {
    sum += ls[i];
  }
  if (sum > t) {
    return -1;
  }

  int best_sum = sum;
  /*std::vector<int> used(ls.size(), 0);
  FindRecursively(t, k, ls, used, 0, best_sum);*/

  std::vector<int> data(k, 1);
  data.resize(ls.size(), 0);
  do {
    sum = 0;
    for (size_t i = 0; i < ls.size(); ++i) {
      if (data[i] == 1) {
        sum += ls[i];
      }
    }
    if (sum <= t) {
      if (sum > best_sum) {
        best_sum = sum;
      }
    }
  } while (std::prev_permutation(data.begin(), data.end()));

  return best_sum;
}

int main(int argc, char* argv[]) {
  /*
    std::vector<int> ts = {50, 55, 56, 57, 58};
    int n = BestTravel::chooseBestSum(163, 3, ts);
    testequal(n, 163);
    ts = {50};
    n = BestTravel::chooseBestSum(163, 3, ts);
    testequal(n, -1);
    ts = {91, 74, 73, 85, 73, 81, 87};
    n = BestTravel::chooseBestSum(230, 3, ts);
    testequal(n, 228);
    n = BestTravel::chooseBestSum(331, 2, ts);
    testequal(n, 178);
    n = BestTravel::chooseBestSum(331, 4, ts);
    testequal(n, 331);
    n = BestTravel::chooseBestSum(331, 5, ts);
    testequal(n, -1);
    n = BestTravel::chooseBestSum(331, 1, ts);
    testequal(n, 91);
    n = BestTravel::chooseBestSum(700, 8, ts);
    testequal(n, -1);
   */
  const std::vector<int> ts1 = {50, 55, 56, 57, 58};
  const std::vector<int> ts2 = {50};
  const std::vector<int> ts3 = {91, 74, 73, 85, 73, 81, 87};
  TestCaseStruct test_cases[] = {{{163, 3, ts1}, 163}, {{163, 3, ts2}, -1},
                                 {{230, 3, ts3}, 228}, {{331, 2, ts3}, 178},
                                 {{331, 4, ts3}, 331}, {{331, 5, ts3}, -1},
                                 {{331, 1, ts3}, 91},  {{700, 8, ts3}, -1}};

  BestTravel solution;
  for (auto& test_case : test_cases) {
    if (solution.chooseBestSum(test_case.input.t, test_case.input.k,
                               test_case.input.ls) ==
        test_case.expected_output) {
      cout << "test case \"t = [" << test_case.input.t << "] k = ["
           << test_case.input.k << "]\" is pass." << std::endl;
    } else {
      cout << "test case \"t = [" << test_case.input.t << "] k = ["
           << test_case.input.k << "]\" is fail." << std::endl;
    }
  }

  return EXIT_SUCCESS;
}

## Result

###### tags: `CodeWars` `C++`