Tyr's blog

By Tyr, 9 years ago,

Hi, I want to generate bit strings of length n and exactly m ones I came up with this algorithm but can't make it more efficient any Idea ? or am I doing optimization right ?

// cin >> number >> no;
// sample input 3 1
// smaple output:
// 0 0 1
// 0 1 0
// 1 0 0

int number, nOnes, no;
int solution[10000];

void backtrack(int n) {
if(n == number) {
if(nOnes == no)
print();
} else {
int candidates[] = {0, 1};
for(int i = 0; i < 2; i++)
{
if(candidates[i] == 1) {
nOnes += 1;
if(nOnes > no){
nOnes--;
return;
}
}
solution[n] = candidates[i];
backtrack(n + 1);
if(candidates[i])
nOnes -= 1;
}
}
}



• +5

 » 9 years ago, # | ← Rev. 2 →   0 O(c(n, k) * n) code
•  » » 9 years ago, # ^ |   +5 Thanks, really helpful.
 » 9 years ago, # |   +4 Why not next_permutation?
•  » » 9 years ago, # ^ |   +8 because I want to practice backtrack ! :)
 » 9 years ago, # |   0 yup, just try next_permutation as suggested by Scalar algo or use c++ STL for this. and feed lowest possible bit string of length n with m ones which will be (n-m) zeroes followed by m ones.