Generate all permutations of given length such that every permutation has more or equal 1’s than 0’s in all prefixes of the permutation.
Generate all permutations of given length such that every permutation has more or equal 1’s than 0’s in all prefixes of the permutation.
Examples:
Input: len = 4 Output: 1111 1110 1101 1100 1011 1010 Note that a permutation like 0101 can not be in output because there are more 0's from index 0 to 2 in this permutation. Input: len = 3 Output: 111 110 101 Input: len = 2 Output: 11 10
Like permutation generation problems, recursion is the simplest approach to solve this. We start with an empty string, attach 1 to it and recur. While recurring, if we find more 1’s at any point, we append a 0 and make one more recursive call.
Output:
1111 1110 1101 1100 1011 1010
Add Comment