一个简单问题的算法该怎么写？

Question

这类帖子好多个http://bbs.csdn.net/topics/380259947

Answer 1

得到组合比较好搞  n！
比如 A, B,C就是3！= 6种 ABC, ACB, BAC, BCA, CAB, CBA但是ABC的输出组合就比较麻烦了  有C(n-1, 0) +C(n-1, 1) + C(n-1, 2) + ...+ C(n-1, n -1)种
--------------------分别插入0个空格，1个空格，2个空格n-1个空格比如ABCD的输出就由 1 + 3 + 3 +1种ABCD、 A BCD、 AB CD、ABC D、A B CD、A BC D、AB C D、A B C D

Answer 2

public void Run() 
        {
            string str = "ABCD";
            List<string> list = A(str);
            list.ForEach(x => { Console.WriteLine(x); });
        }        public Dictionary<string, List<string>> Dic_A = new Dictionary<string, List<string>>();        public List<string> A(string str) 
        {
            if (Dic_A.ContainsKey(str))
            {
                return Dic_A[str];
            }            List<string> list = new List<string>();
            char[] array = str.ToArray();
            if (array.Length == 1)
            {
                list.Add(str);
            }
            else 
            {
                for (int i = 0; i < array.Length; i++)
                {
                    char first = array[i];
                    string tem = new string(array.Take(i).Concat((i == array.Length - 1) ? "" : array.Skip(i + 1)).ToArray());
                    List<string> list_tem = A(tem);
                    for (int j = 0; j < list_tem.Count(); j++)
                    {
                        list.Add(first + " " + list_tem[j]);
                        list.Add(first + list_tem[j]);
                    }
                }
            }
            
            Dic_A.Add(str, list);
            return list;
        }