字符串的全部子序列

题号：NC230164
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

给定一个字符串s，长度为n，求s的所有子序列

1.子序列: 指一个字符串删掉部分字符（也可以不删）形成的字符串，可以是不连续的，比如"abcde"的子序列可以有"ace","ad"等等

2.将所有的子序列的结果返回为一个字符串数组

3.字符串里面可能有重复字符，但是返回的子序列不能有重复的子序列，比如"aab"的子序列只有"","a","aa","aab","ab","b"，不能存在2个相同的"ab"

4.返回字符串数组里面的顺序可以不唯一

数据范围:

$0<=s.length<=16$

要求:时间复杂度为 $O(2^n)$

示例1

复制

"ab"

复制

["","a","ab","b"]

返回["","b","a","ab"]也是可以的，视为正确，顺序不唯一

示例2

复制

"dbcq"

复制

["","b","bc","bcq","bq","c","cq","d","db","dbc","dbcq","dbq","dc","dcq","dq","q"]

示例3

复制

"aab"

复制

["","a","aa","aab","ab","b"]

返回的字符串数组里面不能存在"ab","ab"这样2个相同的子序列