题目链接

　回溯算法定义

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称

题解

我们尝试去改变每一个字母位　将小写转大写　大写转小写
对于每一位只在当前操作线上改变一次

如何避免重复?

在当前操作线上只去改变后置位 map标记

AC代码

class Solution {
public:
    int vis[100] = {0};
    vector<string> res;
    map<string,int> mp;
    void dfs(int a,string S)
    {
        for(int i=a;i<S.length();i++)
        {
            if(!vis[i] && isalpha(S[i]))
            {
                vis[i] = 1;
                char k = S[i];
                if(islower(k))
                    S[i] = toupper(S[i]);
                else if(isupper(k))
                    S[i] = tolower(S[i]);
                if(!mp[S])
                {
                    dfs(a+1,S);
                    res.push_back(S);
                    mp[S]++;
                }
                S[i] = k;
                vis[i] = 0;
            }
        }
    }
    vector<string> letterCasePermutation(string S) {
        dfs(0,S);
        res.push_back(S);
        return res;
    }
};

更优的代码

class Solution {
public:
    vector<string> res;
    void dfs(int i,string s)
    {
        if(i == s.length())
        {
            res.push_back(s);
            return;
        }
        if(!isalpha(s[i]))
            dfs(i+1,s);
        else {
            //大小写都改变 枚举所有情况
            s[i] = toupper(s[i]);
            dfs(i+1,s);
            s[i] = tolower(s[i]);
            dfs(i+1,s);
        }
    }
    vector<string> letterCasePermutation(string S) {
        dfs(0,S);
        return res;
    }
};