Permutations without itertools for two values (using recursion!)

Stackoverflow, I am once again asking for your help.

I'm aware there are other threads about this but I'll explain what makes my assignment different.

Basically my function would get a list of 0s and 1s, and return all the possible orders for the string. For example for "0111" we will get "0111", "1011", "1101", "1110".

Here's my code:

def permutations(string):
    if len(string) == 1:
        return [string]

    lst = []

    for j in range(len(string)):
        remaining_elements = ''.join([string[i] for i in range(len(string)) if i != j])
        mini_perm = permutations(remaining_elements)

        for perm in mini_perm:
            new_str = string[j] + perm
            if new_str not in lst:
                lst.append(new_str)

    return lst

The problem is when I run a string like "000000000011" it takes a very long time to process. There is supposed to be a more efficient way to do it because it's just two numbers. So I shouldn't be using the indexes?

Please help me if you can figure out a more efficient say to do this.

(I am allowed to use loops just have to use recursion as well!)

Here is an example for creating permutations with recursion that is more efficient:

def permute(string):
    string = list(string)
    n = len(string)

    # Base conditions
    # If length is 0 or 1, there is only 1 permutation
    if n in [0, 1]:
        return [string]

    # If length is 2, then there are only two permutations
    # Example: [1,2] and [2,1]
    if n == 2:
        return [string, string[::-1]]

    res = []
    # For every number in array, choose 1 number and permute the remaining
    # by calling permute recursively
    for i in range(n):
        permutations = permute(string[:i] + string[i+1:])
        for p in permutations:
            res.append([''.join(str(n) for n in [string[i]] + p)])

    return res

This should also work for permute('000000000011') - hope it helps!