Как получить все возможные перестановки строки и всех их подстрок?

Question

Я пытаюсь найти все возможные перестановки строки символов и всех их подстрок.Например, учитывая ввод 'abc', функция должна вернуть:

['a', 'b', 'c', 'ab', 'ac', 'ba', 'bc', 'ca', 'cb', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Я пытался часами подряд и не смог найти никакого решения.Не нашел ни одного связанного вопроса.AC # или Java-решение предпочтительнее, но это не имеет большого значения.Псевдокод тоже подойдет.

Answer 1

Решение на самом деле раздражающе простое:

static void permSub(String s, String pre)
{    
  System.out.println(pre);

  if(s.isEmpty()) return;

  for(int i=0; i<s.length(); i++)
    permSub(s.substring(0, i)+s.substring(i+1), pre+s.charAt(i));
}

Тест:

public static void main(String[] args)
{
  permSub("abc", "");
}

Вывод:

a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba

Обратите внимание, что метод также выводит пустой набор, что технически правильно, но вы можете отфильтровать его.