pamital12
BAN USER- 0of 0 votes
AnswersGiven a number N, print all the ways (combinations) to represent the number from the given set of integers.
- pamital12
Ex: Given set is {2,3,7,8,9} and given number N = 7, then the combinations are:
7,2+2+3. Repetitions are not allowed, hence 3+2+2 or 2+3+2 are not allowed.| Report Duplicate | Flag | PURGE
Amazon
DP formulation
void merge( set<string> &s1, set<string> &s2 ) {
set<string>::iterator sIter;
for (sIter = s1.begin(); sIter != s1.end(); ++sIter)
s2.insert(*sIter);
}
void merge( set<string> &s1, string s, set<string> &s2 ) {
s.append("+");
string stemp(s);
set<string>::iterator sIter;
for (sIter = s1.begin(); sIter != s1.end(); ++sIter) {
s.clear();
s.append(stemp);
s.append(*sIter);
s2.insert(s);
}
}
string get_string( int i ) {
stringstream out;
out << i;
return out.str();
}
//PRINT ALL COMBINATIONS OF COIN CHANGE
void All_combinations( int target, int *list, int n ) {
sort(list, list+n);
set<string> sSet;
vector<set<string>> row(target+1);
vector<vector<set<string>>> combination(n+1,row);
vector<set<string>> prev;
vector<set<string>> curr;
sSet.insert("-2");
row.push_back(sSet);
int i, k;
for (i=1; i<=target; ++i) {
sSet.clear();
for (k=1; k<=n; ++k) {
curr = combination[k];
prev = combination[k-1];
if (k>1)
merge(prev[i], sSet);
if ((i-list[k-1])>0){
merge(curr[i-list[k-1]], get_string(list[k-1]), sSet);
}
else if (i==list[k-1])
sSet.insert(get_string(i));
curr[i] = sSet;
combination[k] = curr;
}
}
set<string>::iterator sIter;
cout<<"combinations\n";
//target = 4;
//n = 3;
i=0;
for (sIter = combination[n][target].begin(); sIter != combination[n][target].end(); ++sIter) {
i++;
cout<<*sIter<<endl;
}
cout<<i<<"combinations"<<endl;
}
Here is my implementation of the above dynamic programming approach. I think it works well and also it removes the duplicate combinations.
void merge( set<string> &s1, set<string> &s2 ) {
set<string>::iterator sIter;
for (sIter = s1.begin(); sIter != s1.end(); ++sIter)
s2.insert(*sIter);
}
void merge( set<string> &s1, string s, set<string> &s2 ) {
s.append("+");
string stemp(s);
set<string>::iterator sIter;
for (sIter = s1.begin(); sIter != s1.end(); ++sIter) {
s.clear();
s.append(stemp);
s.append(*sIter);
s2.insert(s);
}
}
string get_string( int i ) {
stringstream out;
out << i;
return out.str();
}
void All_combinations( int target, int *list, int n ) {
sort(list, list+n);
set<string> sSet;
vector<set<string>> row(target+1);
vector<vector<set<string>>> combination(n+1,row);
vector<set<string>> prev;
vector<set<string>> curr;
sSet.insert("-2");
row.push_back(sSet);
int i, k;
for (i=1; i<=target; ++i) {
sSet.clear();
for (k=1; k<=n; ++k) {
curr = combination[k];
prev = combination[k];
if (k>1)
merge(prev[i], sSet);
if ((i-list[k-1])>0){
merge(curr[i-list[k-1]], get_string(list[k-1]), sSet);
}
else if (i==list[k-1])
sSet.insert(get_string(i));
curr[i] = sSet;
combination[k] = curr;
}
}
set<string>::iterator sIter;
cout<<"combinations\n";
//target = 4;
//n = 3;
for (sIter = combination[n][target].begin(); sIter != combination[n][target].end(); ++sIter)
cout<<*sIter<<endl;
}
My answer was based on backtracking.
void get_combinations( int N, int *set, int n, int sum_till_now, int *arry, int length ) {
if (sum_till_now == N) {
print_combination (arry, length);
}
if (sum_till_now > N)
return;
for (int i=0; i<n; ++i) {
arry[length] = set[i];
get_combinations(N, set, n, sum_till_now+set[i], arry, length+1);
}
}
void print_combination( int *arry, int length ) {
cout<<arry[0];
for (int i=1; i<length; ++i ) {
cout<<"+"<<arry[i];
}
cout<<endl;
}
He then asked me about the complexity and i told him that it is exponential in worst case. He then asked if I could solve it in O(n^2) or O(n^3). I couldn't think of a solution. Any suggestions?
- pamital12 June 04, 2011
- pamital12 June 06, 2011