3955. Valid Binary Strings With Cost Limit

You are given two integers n and k.

The cost of a binary string s is defined as the sum of all indices i (0-based) such that s[i] == '1'.

A binary string is considered valid if:

• It does not contain two consecutive '1' characters.
• Its cost is less than or equal to k.

Return a list of all valid binary strings of length n in any order.

class Solution {
    void helper(int p, int n, int c, string& s, vector<string>& res) {
        if(p == n) res.push_back(s);
        else {
            s.push_back('0');
            helper(p+1,n,c,s,res);
            s.pop_back();
            if(s.size() == 0 or s.back() == '0' and c >= p) {
                s.push_back('1');
                helper(p+1,n,c-p,s,res);
                s.pop_back();
            }
        }
    }
public:
    vector<string> generateValidStrings(int n, int k) {
        vector<string> res;
        string s = "";
        helper(0,n,k,s,res);
        return res;
    }
};