LeetCode.77.46.784(递归&回溯)

回溯法模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

77.组合

class Solution {
  public:
    /*vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path;           // 用来存放符合条件结果
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.push_back(i);         // 处理节点
            backtracking(n, k, i + 1); // 递归
            path.pop_back();           // 回溯，撤销处理的节点
        }
    }
    vector<vector<int>> combine(int n, int k) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k, 1);
        return result;
    }*/
    // 27/27 cases passed (20 ms)
    // Your runtime beats 58.58 % of cpp submissions
    // Your memory usage beats 49.67 % of cpp submissions (9.8 MB)
    vector<vector<int>> combine(int n, int k) {
        if (k <= 0 || k > n)
            return {{}};
        vector<vector<int>> ans;
        for (int i = n; i >= k; i--) {
            vector<vector<int>> temp = combine(i - 1, k - 1);
            for (int j = 0; j < temp.size(); j++) {
                temp[j].push_back(i);
                ans.push_back(temp[j]);
            }
        }
        return ans;
        // 27/27 cases passed (56 ms)
        // Your runtime beats 8.88 % of cpp submissions
        // Your memory usage beats 7.7 % of cpp submissions (30.6 MB)
    }
};
/*
回溯法模板
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
*/

46.全排列

class Solution {
  public:
    vector<vector<int>> result;
    vector<int> path;
    vector<int> sample;
    void fun() {
        if (path.size() == sample.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < sample.size(); i++) {
            bool judge = 0;
            for (int j = 0; j < path.size(); j++) {
                if (sample[i] == path[j]) {
                    judge = 1;
                    break;
                }
            }
            if (judge)
                continue;
            path.push_back(sample[i]);
            fun();
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int> &nums) {
        sample = nums;
        fun();
        return result;
    }
    // 26/26 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 63.22 % of cpp submissions (7.6 MB)
};

784.字母大小写全排列

class Solution {
  public:
    /*vector<string> result;
    vector<string> path;
    vector<int> letterPos;
    string sample;
    int isLetter(char a) {
        if (a >= 'a' && a <= 'z')
            return -1;
        if (a >= 'A' && a <= 'Z')
            return 1;
        return 0;
    }
    void fun(int point) {
        if (point >= letterPos.size()) {
            string temp;
            for (int i = 0; i < path.size(); i++) {
                temp += path[i];
            }
            result.push_back(temp);
            return;
        }
        int plus[2] = {0, isLetter(sample[letterPos[point]]) * 32};
        for (int i = 0; i < 2; i++) {
            string temp;
            temp += (char)(sample[letterPos[point]] + plus[i]);
            temp += sample.substr(letterPos[point] + 1, letterPos[point + 1] - letterPos[point] - 1);
            path.push_back(temp);
            fun(point + 1);
            path.pop_back();
        }
    }
    vector<string> letterCasePermutation(string s) {
        for (int i = 0; i < s.size(); i++) {
            if (isLetter(s[i])) {
                letterPos.push_back(i);
            }
        }
        sample = s;
        if (!letterPos.empty())
            path.push_back(sample.substr(0, letterPos[0]));
        else
            path.push_back(sample);
        fun(0);
        return result;
    }*/
    //莫名其妙的overflow，本地调试都是对的
    vector<string> result;
    string scanned;
    int isLetter(char a) {
        if (a >= 'a' && a <= 'z')
            return -1;
        if (a >= 'A' && a <= 'Z')
            return 1;
        return 0;
    }
    void fun(string s) {
        if (s == "") {
            result.push_back(scanned);
            return;
        }
        if (isLetter(s[0])) {
            int plus[2] = {0, isLetter(s[0]) * 32};
            for (int i = 0; i < 2; i++) {
                scanned.push_back(s[0] + plus[i]);
                fun(s.substr(1));
                scanned.pop_back();
            }
        } else {
            scanned.push_back(s[0]);
            fun(s.substr(1));
            scanned.pop_back(); //加了这行就不用使用vector了，void好像默认最后一行return
        }
    }
    vector<string> letterCasePermutation(string s) {
        fun(s);
        return result;
    }
    // 63/63 cases passed (4 ms)
    // Your runtime beats 89.15 % of cpp submissions
    // Your memory usage beats 27.29 % of cpp submissions (11.8 MB)
};