algorithm - 从给定字符串打印按字典顺序排序的子集

Question

例如 - 如果字符串是“abc”，答案应该是 a ab abc ac b bc c(只应出现一组字符中按字典顺序排列的最小组合) 我已经解决了这个问题，但是对于包含 15 个或更多字符的字符串，它会花费很多时间。如何减少算法的运行时间？ 这里，n 是字符串的长度。 这是我的代码:

            int n = int.Parse(Console.ReadLine());
            var str = Console.ReadLine();
            string coll = string.Empty;
            coll = coll + " " + str[0];
            for (int j = 1; j < n; j++)
            {
                var items = coll.Split(' ');
                foreach (var item in items)
                {
                    coll = coll + " " + item+str[j];
                }
            }
            var tt = coll.Split(' ').OrderBy(a => a);
            foreach (var item in tt)
                if (!string.IsNullOrEmpty(item))
                    Console.WriteLine(item);

Answer 1

对于长度为 n 的字符串，有 2^n 个可能的子集。如果需要打印每个子集，您将无法避免指数级的复杂性。