A non-recursive trick for subsets generation IV

Another problem that requires subset generation, and the same non-recursive technique is applied: go from 0 to 2^N-1, creating the subsets. N=12 so very small. I could have used StringBuilder to reduce the mem and processing pressure, but string worked fine too. Code is down below, cheers, ACC.

Valid Binary Strings With Cost Limit - LeetCode

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.

 

Example 1:

Input: n = 3, k = 1

Output: ["000","010","100"]

Explanation:

The binary strings of length 3 without consecutive '1' characters are:

• "000" : cost = 0
• "100" : cost = 0
• "010" : cost = 1
• "001" : cost = 2
• "101" : cost = 0 + 2 = 2

Among these, the strings with cost less than or equal to k = 1 are "000", "010" and "100".

Thus, the valid strings are ["000", "010", "100"].

Example 2:

Input: n = 1, k = 0

Output: ["0","1"]

Explanation:

The valid binary strings of length 1 are "0" and "1".

Thus the answer is ["0", "1"].

 

Constraints:

• 1 <= n <= 12
• 0 <= k <= n * (n - 1) / 2

public class Solution {
    public IList GenerateValidStrings(int n, int k)
    {
        List retVal = new List();

        int p = (int)Math.Pow(2, n);
        for (int i = 0; i < p; i++)
        {
            int temp = i;
            string s = "";
            bool valid = true;
            while (temp > 0)
            {
                int d = temp % 2;
                if (d == 1 && s.Length > 0 && s[0] == '1')
                {
                    valid = false;
                    break;
                }
                s = d.ToString() + s;
                temp /= 2;
            }

            if (valid)
            {
                while (s.Length < n)
                    s = "0" + s;

                int cost = 0;
                for (int j = 0; j < s.Length; j++)
                {
                    if (s[j] == '1')
                        cost += j;
                    if (cost > k)
                    {
                        valid = false;
                        break;
                    }
                }
            }

            if (valid)
            {
                retVal.Add(s);
            }
        }

        return retVal;
    }
}