1class Solution {
2    // Target length of each binary string.
3    private int n;
4    // Threshold used to bound the accumulated index sum of placed '1' characters.
5    private int k;
6    // Collects all valid generated strings.
7    private List<String> ans;
8    // Mutable buffer representing the current candidate string being built.
9    private StringBuilder path;
10
11    public List<String> generateValidStrings(int n, int k) {
12        this.n = n;
13        this.k = k;
14        this.ans = new ArrayList<>();
15        this.path = new StringBuilder();
16
17        // Start the depth-first search from index 0 with an accumulated total of 0.
18        dfs(0, 0);
19
20        return ans;
21    }
22
23    /**
24     * Builds candidate strings character by character.
25     *
26     * @param index the current position to fill in the string
27     * @param total the running sum of indices at which '1' characters were placed
28     */
29    private void dfs(int index, int total) {
30        // A full-length string has been formed; record it.
31        if (index >= n) {
32            ans.add(path.toString());
33            return;
34        }
35
36        // Branch 1: place a '0' at the current position (always allowed).
37        path.append('0');
38        dfs(index + 1, total);
39        path.deleteCharAt(path.length() - 1);
40
41        // Branch 2: place a '1' only if the previous character is not '1'
42        // (preventing two consecutive '1's) and the index-sum constraint holds.
43        if ((path.length() == 0 || path.charAt(path.length() - 1) == '0')
44                && total + index <= k) {
45            path.append('1');
46            dfs(index + 1, total + index);
47            path.deleteCharAt(path.length() - 1);
48        }
49    }
50}
51

1class Solution {
2public:
3    vector<string> generateValidStrings(int n, int k) {
4        vector<string> result;  // Stores all valid generated strings
5        string path;            // Current string being built during DFS
6
7        // Recursive depth-first search.
8        // index    : current position in the string (0-based)
9        // weightSum: accumulated weighted sum of positions where '1' was placed
10        auto dfs = [&](this auto&& dfs, int index, int weightSum) -> void {
11            // Base case: a full-length string has been built
12            if (index >= n) {
13                result.push_back(path);
14                return;
15            }
16
17            // Branch 1: place '0' at the current position (always allowed)
18            path.push_back('0');
19            dfs(index + 1, weightSum);
20            path.pop_back();
21
22            // Branch 2: place '1' at the current position, allowed only when:
23            //   - the previous character is '0' (or the string is empty),
24            //     i.e. no two consecutive '1's,
25            //   - and adding the current position index keeps the weighted
26            //     sum within the limit k.
27            if ((path.empty() || path.back() == '0') && weightSum + index <= k) {
28                path.push_back('1');
29                dfs(index + 1, weightSum + index);
30                path.pop_back();
31            }
32        };
33
34        // Start the search from position 0 with an empty weighted sum
35        dfs(0, 0);
36
37        return result;
38    }
39};
40

1// Stores all valid binary strings that satisfy the constraints
2const result: string[] = [];
3
4// Tracks the current path (sequence of characters) during DFS traversal
5const currentPath: string[] = [];
6
7/**
8 * Depth-first search to build valid strings character by character.
9 *
10 * @param index           The current position being filled (0-based).
11 * @param indexSumOfOnes  The accumulated sum of indices where '1' has been placed.
12 */
13const dfs = (index: number, indexSumOfOnes: number): void => {
14    // Base case: a complete string of length n has been built
15    if (index >= n) {
16        result.push(currentPath.join(''));
17        return;
18    }
19
20    // Option 1: always allowed to place a '0' at the current position
21    currentPath.push('0');
22    dfs(index + 1, indexSumOfOnes);
23    currentPath.pop();
24
25    // Option 2: place a '1' only if two conditions hold:
26    //   a) the previous character is '0' (or path is empty), preventing consecutive '1's
27    //   b) adding this index keeps the running sum within the limit k
28    const previousIsZero =
29        currentPath.length === 0 ||
30        currentPath[currentPath.length - 1] === '0';
31
32    if (previousIsZero && indexSumOfOnes + index <= k) {
33        currentPath.push('1');
34        dfs(index + 1, indexSumOfOnes + index);
35        currentPath.pop();
36    }
37};
38
39/**
40 * Generates all valid binary strings of length n under the given constraints:
41 *   - No two consecutive '1' characters.
42 *   - The sum of indices at which '1' appears must not exceed k.
43 *
44 * @param n  The length of each generated string.
45 * @param k  The upper bound for the sum of indices where '1' is placed.
46 * @returns  An array of all valid binary strings.
47 */
48function generateValidStrings(n: number, k: number): string[] {
49    // Reset shared state in case the function is invoked multiple times
50    result.length = 0;
51    currentPath.length = 0;
52
53    // Start the recursive search from position 0 with an empty index sum
54    dfs(0, 0);
55
56    return result;
57}
58