combinations - 如何获得字符串及其所有子字符串的所有可能排列？

Question

我正在尝试查找字符串及其所有子字符串的所有可能排列。例如，给定输入“abc”，该函数应返回：

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

我一直在尝试几个小时，但找不到任何解决方案。也没有找到任何相关的问题。首选 AC# 或 Java 解决方案，但这并不重要。伪代码也可以。

标签： combinationspermutation

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

请注意，该方法也输出空集，这在技术上是正确的，但您可能希望将其过滤掉。