Generate all strings having characters a,b or c with length equal to n with atmost 1 b and 2 c

Question

Generate all strings with the following constrains

• Length: n
• Characters allowed: a,b,c
• At most one b
• At most two c

I have written the following code

def generate(s,counta,countb,countc,n,result):
    if counta+countb+countc==n:
        print(counta,countb,countc)
        result.append(s)
        print(s)
        return
    if counta+countb+countc<n and counta<=n:
        generate(s+"a",counta+1,countb,countc,n,result)
    if counta+countb+countc<n and countb<=1:
        generate(s+"b",counta+1,countb+1,countc,n,result)
    if counta+countb+countc<n and countc<=2:
        generate(s+"c",counta,countb,countc+1,n,result)


result=[]
generate("",0,0,0,3,result)
print(result)

I get the following result which I don't understand why. Some strings of length less than n are getting added to the result.

['aaa', 'aac', 'ab', 'aca', 'acc', 'ba', 'bc', 'caa', 'cac', 'cb', 'cca', 'ccc']

Update Code: (Working)

def generate(s,counta,countb,countc,n,result):
if counta+countb+countc==n:
    # print(counta,countb,countc)
    result.append(s)
    # print(s)
    return
if counta+countb+countc<n and counta<=n:
    generate(s+"a",counta+1,countb,countc,n,result)
if counta+countb+countc<n and countb<1:
    generate(s+"b",counta,countb+1,countc,n,result)
if counta+countb+countc<n and countc<2:
    generate(s+"c",counta,countb,countc+1,n,result)

result=[]
generate("",0,0,0,3,result)
print(result)

Output:

['aaa', 'aab', 'aac', 'aba', 'abc', 'aca', 'acb', 'acc', 'baa', 'bac', 'bca', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbc', 'cca', 'ccb']

Answer 1

Some of your logic is off; for example, countb<=1 means you could already have a b, so you shouldn't necessarily add another. Also, in that call, you are adding 1 to both countb and countc.