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;
}
}
}
O(c(n, k) * n) code
Thanks, really helpful.
Why not next_permutation?
because I want to practice backtrack ! :)