【Leetcode打卡】递归回溯

784. 字母大小写全排列

class Solution {
public:
    int find(string s,int pos)
    {
        int i=pos;
        while(i<s.size())
        {
            if(isalpha(s[i]))
            {
                return i;
            }
            ++i;
        }
        return -1;
    }
    void turn(string& s,int pos)
    {
        if(islower(s[pos]))
        {
            s[pos]=toupper(s[pos]);
        }
        else
        {
            s[pos]=tolower(s[pos]);
        }
    }
    vector<string> save;
    void dfs(string s,int pos)
    {
        pos=find(s,pos);
        if(pos==-1)
        {
            save.push_back(s);
            return;
        }
        //说明有字母       
        turn(s,pos); 
        dfs(s,pos+1);
        turn(s,pos);
        dfs(s,pos+1);
    }
    vector<string> letterCasePermutation(string s) {
        dfs(s,0);
        return save;
    }
};

LCR 081. 组合总和

class Solution {
public:
    vector<vector<int> > save;
    int sum=0;
    vector<int> path;
    void dfs(vector<int>& v,int target,int pos)
    {
        if(sum==target)
        {
            save.push_back(path);
            return;
        }
        if(sum>target)
        {
            return;
        }
        for(int i=pos;i<v.size();++i)
        {
            sum+=v[i];
            path.push_back(v[i]);
            dfs(v,target,i);
            path.pop_back();
            sum-=v[i];
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            sort(candidates.begin(),candidates.end());
            dfs(candidates,target,0);
        return save;
    }
};