viiids
BAN USERTwo solutions, one with complexity 2^n and the other with n!
Soln 1:
//input
arr[]
k
vector<set<string> > s;
void generateSets(set<int> v,int n,int ind) {
if(n == k) {
s.push_back(v);
}
if(ind == v.size()) return;
else {
generateSets(v,n+1,ind+1);
v.insert(arr[ind])
generateSets(v,n+1,ind+1);
}
}
//method call
generateSets(new set<int>(),0,0);
Soln 2:
//input
vector<int> arr
k
vector<set<int> > generateSets() {
sort(arr.begin(),arr.end());
set<int> s;
do {
for(int i=0;i<k;i++) {
v.insert(arr[i]);
}
s.push_back(v);
} while(next_permutation(arr.begin(),arr.end()));
}
The recurrence relation should be
dp[i][j] = max number of strings such that when concatenated, they contain i Xs and j Ys.
Then
initialize dp[][] with -1
dp[0][0] = 0;
for(i = 0 to 3) {
for(j = 0 to 2) {
for(all strings as string){
nX = countX(string);
nY = countY(string);
if(nX >=i && nY >= j)
dp[i][j] = max(dp[i-nX][j-nY]+1,dp[i][j]);
}
}
}
dp[3][2] should be yor answer.
O(n^2) for an array in decreasing order.
- viiids July 20, 2013