Generate Binary strings of given length and with a constraint

Question

I am trying to write a logic where I want to generate a list of binary strings of given size n and also the string should have maximum of k bits set to 1.

Example:

If n = 3, k = 1 ==> the number of 1's can be 0 or 1.
Then the output should be 000, 001, 010, 100

Below is the logic I have used with the help of this link as a reference:

Here n is same as arr.length.

static void generateAllBinaryStrings(int n, int arr[], int i, List<String> res, int k) {
    if (i == n) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int j = 0; j < arr.length; j++) {
            int val = arr[j];
            if (val == 1) {
                count++;
            }
            sb.append(val);
        }
        if (count <= k) {
            res.add(sb.toString());
        }

        return;
    }

    arr[i] = 0;
    generateAllBinaryStrings(n, arr, i + 1, res, k);

    arr[i] = 1;
    generateAllBinaryStrings(n, arr, i + 1, res, k);
}

public static void main(String args[]) {
    int n = 3;
    int[] arr = new int[n];
    int k = 1;
    int i = 0;
    List<String> res = new ArrayList<>();
    generateAllBinaryStrings(n, arr, i, res, k);
    System.out.println(res);// Prints [000, 001, 010, 100]
}

This code is working fine, but this logic generates all possible binary string then filters based on the number of 1's in the string.

Is there any less time complex algorithm for this problem.

@MauricePerry, yes `n` is same as `arr.length`. I have updated question with this point. — learner, Oct 11 '19 at 05:15
you can iterate from j=0 to k, and for each j generate strings which can have j bits 1. nCj and rest will be zero. when k=n we need to gerenate all possible strings: nC0 + nC1 + nC2 + ... nCn = 2^n which is worst case time complexity. — Mohd Waseem, Oct 11 '19 at 05:19
seems what you want is a permutation of the original string containing as many 1 as desired. For a long list of answers see [this](https://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string) and [this](https://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string) — Curiosa Globunznik, Oct 11 '19 at 05:32

score 0 · Answer 1 · answered Oct 11 '19 at 05:37

The basic thing that comes into my mind while you are trying to generate the string with having this much data with you why cant you just have one more reference to your recursive call that tell how many 1 are there in you generated string as of the recursion in being called.

The method signature now might look like -

static void generateAllBinaryStrings(int n, int arr[], int i, List<String> res, int k,int currentCountOfOnes){
       // Rest logic remains same , each time you don't have to check how many 1's
      // are there as of the call made.

}

This might reduce complexity a bit more than what you have. And one more obvious thing that you can think of is storing your previous called result (memorization -> that leads to a thought of dynamic programming)

Hope thoughts might have helped you.

Note : I could have coded all this but then there is no use of doing so. Try it out if you find it useful do let me know !!

Maurice Perry · Answer 2 · 2019-10-11T08:47:23.300

I've come up with this:

static void generateAllBinaryStrings(StringBuilder sb, int n, Set<String> res, int k) {
    int len = sb.length();
    if (k == 0) {
        repeat(sb, '0', n);
        res.add(sb.toString());
        sb.setLength(len);
    } else {
        for (int i = 0; i <= n; ++i) {
            repeat(sb, '0', i);
            if (i < n) {
                sb.append('1');
                generateAllBinaryStrings(sb, n-i-1, res, k-1);
            } else {
                res.add(sb.toString());
            }
            sb.setLength(len);
        }
    }
}

private static void repeat(StringBuilder sb, char c, int n) {
    for (int j = 0; j < n; ++j) {
        sb.append('0');
    }
}

The idea is that you have k ones to place in a string of length n; so if k == 0, the only possible value is n zeroes. If k > 0, you can add n zeroes, or i zeros, i being anywhere between 0 and n-1, followed by a 1, recurse for the remaining space and k-1.

Generate Binary strings of given length and with a constraint

2 Answers2