1
class Solution {
2
  int dp[1 << 16];
3
  int dfs(unordered_map<int, int> &c, int mask, int &k, int &n) {
4
    if (dp[mask] != -1) return dp[mask];
5
    int canJoin = 0, canNotJoin = 0;
6
    vector<int> canJoinVec;
7
    for (auto [key, value] : c) {
8
      if (((value & mask) == value) and !(mask & (1 << key))) {
9
        // get course we can listen
10
        canJoin |= 1 << key;
11
        canJoinVec.push_back(key);
12
      } else if (!(mask & (1 << key))) {
13
        // get courses we can not listen yet
14
        canNotJoin |= 1 << key;
15
      }
16
    }
17
    // if there is no course we can not listen calculate immediatly
18
    if (!canNotJoin) {
19
      int left = n - bitset<16>(mask).count();
20
      return dp[mask] = left / k + (left % k ? 1 : 0);
21
    }
22
    // if there is some courses we can listen now (less then k) and can not
23
    // listen select the courses we can listen now first
24
    if (bitset<16>(canJoin).count() <= k) {
25
      int nMask = mask | canJoin;
26
      int left = k - bitset<16>(canJoin).count();
27
      // if there is some extra slots we can listen in this semester
28
      // pick any thing
29
      for (int i = 0; i < n and left; i++) {
30
        if (!(canNotJoin & (1 << i)) and !(nMask & (1 << i))) {
31
          nMask |= 1 << i;
32
          left--;
33
        }
34
      }
35
      return dp[mask] = 1 + dfs(c, nMask, k, n);
36
    }
37
    // if we can listen more then k courses now, pick K courses from list (check
38
    // every combinations) any idea for pick m element from n array?
39
    sort(canJoinVec.begin(), canJoinVec.end());
40
    int mi = INT_MAX;
41
    do {
42
      int nMask = mask;
43
      for (int i = 0; i < k; i++) nMask |= 1 << canJoinVec[i];
44
      mi = min(mi, dfs(c, nMask, k, n));
45
    } while (next_permutation(canJoinVec.begin(), canJoinVec.end()));
46
    return dp[mask] = 1 + mi;
47
  }
48

49
 public:
50
  int minNumberOfSemesters(int n, vector<vector<int>> &relations, int k) {
51
    unordered_map<int, int> course;
52
    memset(dp, -1, sizeof(dp));
53
    // initialize courses relational graph
54
    for (auto &r : relations) course[r[1] - 1] |= 1 << (r[0] - 1), course[r[0] - 1] += 0;
55
    dp[(1 << n) - 1] = 0;
56

57
    return dfs(course, 0, k, n);
58
  }
59
};