Applying subproblem technique to permutations with grouping
The subproblems can be broken down as follows.

f0 :- Number of available 0s.

f1 :- Number of available 1s.

ld :- The last digit of the string generated till now.

dp[f1][f0+f1][0] = dp[f1][f0+f1-1][0] + dp[f1-1][f0+f1-1][1]

dp[f1][f0+f1][1] = dp[f1-2][f0+f1-2][0] + dp[f1-1][f0+f1-1][1]


which basically boils down to,

Say at any step the string is S0

then S011 and S00 are valid as well.

Similarly,

if the string is S1 then S11 and S10 are valid as well.

The following code solves the given problem recursively.

def rec(f0,f1,stn): # Frequency of 0,Frequency of 1, List to store generated output
  if f0==0 and f1==0:
    print(''.join(stn))
    return -1;
  if len(stn)==0 or stn[-1]=='0':
    if f0&gt;0:
      rec(f0-1,f1,[x for x in stn]+['0'])
    if f1&gt;1:
      rec(f0,f1-2,[x for x in stn]+['1','1'])
  else:
    if f1&gt;0:
      rec(f0,f1-1,[x for x in stn]+['1'])
    if f0&gt;0:
      rec(f0-1,f1,[x for x in stn]+['0'])

rec(4,4,[])


You can easily solve the overlapping subproblems issue by using a dp-table along with the propagation rules listed above.

Output of the code for a string with 4 1s and 4 0s:-

00001111
00011110
00011011
00111100
00110011
00110110
01111000
01100011
01100110
01101100
11110000
11000011
11000110
11001100
11011000