Determinar todas as sequencias

A solução pode ser definida com recursão. Vou te dar o esqueleto da solução:

List<String> permutar (String prefixo, String sufixo) {
    // caso base: e se não existir sufixo?
    if (?) return ?;
    List<String> resultado = new ArrayList<>();
    for (cada elemento do suffixo) {
        // move o elemento escolhido do sufixo para o prefixo e recorre
        // adiciona o resultado na lista de resultado
        resultado.addAll(?);
    }
    return resultado;
}

E para invocar:

permutar("", suaString);

O que é o sufixo e o prefixo?

O prefixo é a parte “travada” que você escolheu até aquele momento. Por exemplo, se sua string é “1234” (ou pode ser com listas também, fiz com string para ilustrar). No começo, você pode escolher seguir por 4 caminhos para o primeiro elemento: 1, 2, 3 ou 4. Quando você escolhe um deles, aquele elemento passa a ser o prefixo e você tem um novo problema: permutar os outros 3 que sobraram.

Digamos que você escolha o número 1. Nesse momento, seu prefixo é “1” e seu sufixo é “234”. É só continuar movendo elementos do sufixo pro prefixo de forma recursiva. Continuando, podemos pegar o elemento 3. Nesse caminho, o prefixo é “13” e o sufixo “24”. No final, você vai chegar num ponto onde não tem mais sufixo e está tudo no prefixo: quando isso acontecer, você tem uma permutação.

É como se fosse uma árvore. Cada caminho que você escolhe reduz o tamanho do problema em 1 elemento. As soluções são as folhas da árvore.