public class Solution
{
public IList<IList<string>> Partition(string s)
{
if (s.Length == 0)
return new List<IList<string>>();
var part = new bool[s.Length, s.Length];
part[0, 0] = true;
for (var i = 1; i < s.Length; i++)
part[i, i] = part[i, i - 1] = true;
for (var i = 1; i < s.Length; i++)
for (var j = 0; j < s.Length - i; j++)
part[j, i + j] = part[j + 1, i + j - 1] && s[j] == s[i + j];
var ret = new List<IList<string>>();
var temp = new List<string>(s.Length);
Foo(ret, temp, 0, part, s);
return ret;
}
void Foo(List<IList<string>> ret, IList<string> temp, int index, bool[,] part, string s)
{
if (index == s.Length)
{
ret.Add(new List<string>(temp));
}
else
{
for (var i = index; i < s.Length; i++)
{
if (!part[index, i])
continue;
temp.Add(s[index..(i + 1)]);
Foo(ret, temp, i + 1, part, s);
temp.RemoveAt(temp.Count - 1);
}
}
}
}