Блог пользователя Tyr

Автор Tyr, 11 лет назад, По-английски

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
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

O(c(n, k) * n) code

»
11 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится