# Help me solve this question asked in my interview

Given a 2D integer array B of size A*A where

B[i][j] = 1 if the jth gift does not make the ith child happy.

B[i][j] = 2 if the jth gift makes the ith child happy. B[i][j]=3 if the jth gift makes the ith child super happy.

Problem Constraints

1 <= A <= 13

Input Format

The first argument is a single integer A. The second argument is a 2D integer array B.

Output Format

Return a single integer that is among all the combinations of gifting these A gifts to A children which combinations made all A children happy or made at least one child super happy.

Example Input

Input 1

A * 2

-[[2, 2],

[2, 1] ]

Input 2:

A= 3

• [[1, 1, 3] ,[2, 2, 3], [1, 3, 3 ]]

Example Output

Output 1:-
1
Output 2:
6
Example Explanation

Explanation 1:-

Only possible combination of gifting is [2, 1]

Explanation 2:-

The possible combinations of gifting are [3, 1, 2], [3, 2, 1], [1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1)

give an approach to solve this problem

To solve this problem in C++, you can use dynamic programming to find the maximum number of children that can be made happy by selecting the appropriate gifts. Here’s a C++ code snippet to achieve this:
include <bits/stdc++.h>
using namespace std;

int maxHappyChildren(int A, vector<vector> &B) {
vector<vector> dp(1 << A, vector(A, 0));

``````for (int mask = 0; mask < (1 << A); ++mask) {
for (int child = 0; child < A; ++child) {
if (child == 0) {
}
}
} else {
}
}
}
}
}

int maxHappiness = 0;
if (dp[mask][A - 1] >= 2) {
}
}

return maxHappiness;
``````

}

int main() {
int A;
cin >> A;
vector<vector> B(A, vector(A));
for (int i = 0; i < A; ++i) {
for (int j = 0; j < A; ++j) {
cin >> B[i][j];
}
}

``````int result = maxHappyChildren(A, B);
cout << result << endl;

return 0;
``````

}

1 Like

is it working