题意理解

输出一个字符串的所有子串。注意重复出现的子串只保留一个。

方法一

深度优先搜索
每一个字符都有2种情况，选择或者不选择。我们遍历字符串s中的所有字符，每个字符用递归尝试两种调用（选或者不选）。递归的边界条件是遍历到最后一个字符，将得到的子串加入到答案中，然后再回退并进行另一条支路上的递归。

深度优先搜索的示意图如下，字符串为"ab"，边上"0"表示不选，"1"表示选：

最后对包含了所有答案的数组进行排序并去重。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> ans;
    void dfs(string s, int k, string sub) {
        if (k==s.size())
        {
            ans.push_back(sub);
            return;
        }
        //当前字符不加入子串
        dfs(s, k+1, sub);
        //当前字符加入子串
        dfs(s, k+1, sub+s[k]);
        return;
    }
    
    vector<string> generatePermutation(string s) {
        // write code here
        dfs(s, 0, "");
        //排序并删除重复子串
        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        return ans;
    }
};

时间复杂度： $O(2^N\ast \log 2^N)O(2^N*\backslash log\{\{2^N\}\})$。一共有$2^{N}2^N$种情况，对所有的情况进行一次快排，N为字符串长度。
空间复杂度： $O(2^N)O(2^N)$。开辟了新的空间存储最终答案，一共有$2^{N}2^N$个子串。

方法二

优化
我们使用map<string,bool>类型的变量来记录某个子串是否已经出现过。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    unordered_map<string, bool> get;
    vector<string> ans;
    void dfs(string s, int k, string sub) {
        if (k==s.size())
        {
            if (get.find(sub)==get.end())
            {
                get[sub] = true;
                ans.push_back(sub);
            }
            return;
        }
        dfs(s, k+1, sub);
        dfs(s, k+1, sub+s[k]);
        return;
    }
    
    vector<string> generatePermutation(string s) {
        // write code here
        dfs(s, 0, "");
        return ans;
    }
};

时间复杂度： $O(2^N)O(2^N)$。一共有$2^{N}2^N$种情况，每个情况都要判断是否已经提取出来了。N为字符串长度。
空间复杂度： $O(2^N)O(2^N)$。开辟了新的空间记录某个子串是否出现过，以及存储最终答案，一共有$2^{N}2^N$个子串。

方法二