Start learning free

LESSON 288 OF 409 · BACKTRACKING

Generate Binary Strings With K Ones in C++ (Time Complexity: O(2^N))

Practice O(2^n) Read the full explanation

Given two non-negative integers N and K, return the binary strings of length N with exactly K ones.

Example:

Input: N = 4, K = 2
Output: [
    "0011",
    "0101",
    "0110",
    "1001",
    "1010",
    "1100"
]
Notes: K <= N <= 20
STEP 1 OF 11
    Ctrl + Enter to check

    C++ · BACKTRACKING

    Generate Binary Strings With K Ones in C++, explained

    Understanding the Problem

    The core challenge of this problem is to generate all possible binary strings of length N that contain exactly K ones. This problem is significant in various fields such as combinatorics, coding theory, and computer science, where binary representations are frequently used.

    Potential pitfalls include ensuring that the generated strings are of the correct length and contain the exact number of ones specified. Misunderstanding the constraints or the problem requirements can lead to incorrect solutions.

    Approach

    To solve this problem, we can use a backtracking approach. The idea is to build the binary string one bit at a time, ensuring that we do not exceed the required number of ones.

    Here is a step-by-step approach:

    • Start with an empty string and recursively add '0' or '1' to it.
    • Keep track of the number of ones added so far.
    • If the number of ones exceeds K, backtrack.
    • If the length of the string reaches N and it contains exactly K ones, add it to the result list.

    This approach ensures that we explore all possible combinations while adhering to the constraints.

    Algorithm

    Here is a detailed breakdown of the algorithm:

    1. Define a recursive function that takes the current string, the number of ones added so far, and the current length of the string.
    2. If the current length equals N and the number of ones equals K, add the string to the result list.
    3. If the current length is less than N, recursively add '0' and '1' to the string and update the count of ones accordingly.
    4. Ensure that the number of ones does not exceed K at any point.

    Code Implementation

    #include <iostream>
#include <vector>
#include <string>

using namespace std;

// Helper function to generate binary strings
void generateBinaryStrings(int N, int K, string current, int onesCount, vector<string>& result) {
    // Base case: if the current string length is N
    if (current.length() == N) {
        // Check if the current string has exactly K ones
        if (onesCount == K) {
            result.push_back(current);
        }
        return;
    }

    // Add '0' to the current string and recurse
    generateBinaryStrings(N, K, current + "0", onesCount, result);

    // Add '1' to the current string and recurse
    if (onesCount < K) {
        generateBinaryStrings(N, K, current + "1", onesCount + 1, result);
    }
}

// Function to return all binary strings of length N with exactly K ones
vector<string> generateBinaryStrings(int N, int K) {
    vector<string> result;
    generateBinaryStrings(N, K, "", 0, result);
    return result;
}

int main() {
    int N = 4, K = 2;
    vector<string> result = generateBinaryStrings(N, K);

    // Print the result
    for (const string& str : result) {
        cout << str << endl;
    }

    return 0;
}

    Complexity Analysis

    The time complexity of this approach is O(2^N) because we explore all possible binary strings of length N. The space complexity is O(N) due to the recursion stack and the storage of the result list.

    Edge Cases

    Consider the following edge cases:

    • N = 0, K = 0: The output should be an empty string.
    • K > N: This is an invalid case as we cannot have more ones than the length of the string.
    • K = 0: The output should be a string of all zeros.

    Testing

    To test the solution comprehensively, consider the following test cases:

    • Simple cases with small values of N and K.
    • Edge cases as discussed above.
    • Cases where N is at its maximum value (20).

    Using a testing framework like Google Test can help automate and manage these test cases effectively.

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Break down the problem into smaller, manageable parts.
    • Use recursion and backtracking to explore all possible solutions.
    • Keep track of constraints and ensure they are not violated during the solution process.
    • Practice similar problems to improve problem-solving skills and familiarity with common algorithms.

    Conclusion

    Generating binary strings with a specific number of ones is a classic problem that helps in understanding recursion and backtracking. By breaking down the problem and systematically exploring all possibilities, we can arrive at the correct solution. Practicing such problems enhances problem-solving skills and prepares one for more complex challenges.

    Additional Resources

    For further reading and practice, consider the following resources:

    • LeetCode - A platform for practicing coding problems.
    • GeeksforGeeks - A comprehensive resource for learning algorithms and data structures.
    • Coursera - Online courses on algorithms and computer science.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free