递归分析

基础递归分析

字符串子序列+去重

java实现

//从s[i....]后的数加入path，回到上一层递归时需删除最后
public static void f1(char[] s, int i, StringBuilder path, HashSet<string> set){
    if(i == s.length){
        set.add(path.toString();)
    }
    else{
        path.append(s[i]);
        f1(s, i + 1， path, set);
        path.deleteCharAt(path.length()-1);
        f1(s, i+1, path, set);
    }
}

public static String[] generatePermutation1(String str){
    char[] s = str.toCharArray();
    HashSet<String> set = new HashSet<>();
    f1(s, 0, new StringBuilder(), set);
    int m = set.size();
    String[] ans = new String[m];
    int i = 0;
    for(String cur : set){
        ans[i++] = cur;
    }
    return ans;
}

cpp实现

void f1(const std::vector<char>& s, int i, std::string& path, std::unordered_set<std::string>& set) {
    if (i == s.size()) {
        set.insert(path);
    } else {
        path.push_back(s[i]);
        f1(s, i + 1, path, set);
        path.pop_back();
        f1(s, i + 1, path, set);
    }
}