← 返回 microsoft 的题目列表Generate Lexicographically Sorted String Subsets
类型：online_judge
Given a string s of length n, treat each character as an element that can either be selected or skipped. Selected characters must preserve their relative order from the original string.
Generate every subset (i.e., every subsequence), including the empty string. Sort all generated results in lexicographical order and print one result per line.
To avoid duplicate output, assume all characters in s are distinct.
Input Format
One line containing s.
Output Format
Print all subsets in lexicographical order, one per line. The empty string must also be printed, so the first output line may be blank.
Constraints
0 <= len(s) <= 20
Characters in s are distinct
Example 1
Input:
abc
Output:
a
ab
abc
ac
b
bc
c
Example 2
Input:
cab
Output:
a
ab
b
c
ca
cab
cb
Example
Input
abc
Output
a
ab
abc
ac
b
bc
c