回溯算法

回溯算法

77 组合

方法1：回溯

一开始集合是 1，2，3，4， 从左向右取数，取过的数，不再重复取。第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。

• 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
• 图中可以发现n相当于树的宽度，k相当于树的深度。
• 图中每次搜索到了叶子节点，我们就找到了一个结果。
• 只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

int型变量startIndex，这个参数用来记录下一层递归，搜索的起始位置。

终止条件

path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。此时用result二维数组，把path保存起来，并终止本层递归。

class Solution {
public:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int n, int k, int startIndex) { // startIndex来记录下一层递归，搜索的起始位置。

        // path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。
        // 此时用result二维数组，把path保存起来，并终止本层递归。
        if (path.size() == k) {
            result.push_back(path);
            return;
        }

        // backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。
        for (int i = startIndex; i <= n; ++i) { // 控制树的横向遍历
            path.push_back(i); // 处理节点 
            backtracking(n, k, i + 1);  // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }

    vector<vector<int>> combine(int n, int k) {
        result.clear(); // 可以不写
        path.clear();
        backtracking(n, k, 1);
        return result;
    }
};

216 组合总和III

方法1：回溯

本题k相当于树的深度，9（因为整个集合就是9个数）就是树的宽度。

class Solution {
private:
    vector<vector<int>> result; // 存放结果集
    vector<int> path; // 符合条件的结果
    // targetSum：目标和，也就是题目中的n。
    // k：题目中要求k个数的集合。
    // sum：已经收集的元素的总和，也就是path里元素的总和。
    // startIndex：下一层for循环搜索的起始位置。
    void backtracking(int targetSum, int k, int sum, int startIndex) {

        // 如果path.size() 和 k相等了，就终止。
        // 如果此时path里收集到的元素和（sum） 和targetSum（就是题目描述的n）相同了，就用result收集当前的结果。
        if (path.size() == k) {
            if (sum == targetSum) result.push_back(path);
            return; // 如果path.size() == k 但sum != targetSum 直接返回
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i; // 处理
            path.push_back(i); // 处理
            backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
            sum -= i; // 回溯
            path.pop_back(); // 回溯
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear(); // 可以不加
        path.clear();   // 可以不加
        backtracking(n, k, 0, 1);
        return result;
    }
};

17 电话号码的字母组合

方法1：回溯

1. 数字和字母如何映射
2. 两个字母就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来
3. 输入1 * #按键等等异常情况

输入1 * #按键等等异常情况，代码中最好考虑这些异常情况，如果是现场面试，一定要考虑到

// 版本一
class Solution {
private:
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
public:
    vector<string> result;
    string s;
    void backtracking(const string& digits, int index) {
        // 确定终止条件
        // 例如输入用例"23"，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集。
        // 那么终止条件就是如果index 等于 输入的数字个数（digits.size）了（本来index就是用来遍历digits的）。然后收集结果，结束本层递归。
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }

        // index指向的数字，并找到对应的字符集（手机键盘的字符集）
        int digit = digits[index] - '0';        // 将index指向的数字转为int
        string letters = letterMap[digit];      // 取数字对应的字符集
        for (int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]);            // 处理
            backtracking(digits, index + 1);    // 递归，注意index+1，一下层要处理下一个数字了
            s.pop_back();                       // 回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        s.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};

30 组合的总和

方法1：回溯

// 版本一
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    // 一个集合里来求组合的话，就需要startIndex
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {

        // 从叶子节点可以清晰看到，终止只有两种情况，sum大于target和sum等于target。
        if (sum > target) {
            return;
        }
        if (sum == target) {
            // sum等于target的时候，需要收集结果
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i < candidates.size(); i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

131 分割回文串

方法1：回溯

class Solution {
public:
    vector<vector<string>> result;
    vector<string> path;
    void backtracking(const string& s, int startIndex) {
        // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
        if (startIndex >= s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            // 判断这个子串是不是回文，如果是回文，就加入在vector<string> path
            if (isPalindrome(s, startIndex, i)) {
                // 在for循环中，定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            }
            else { // 如果不是则直接跳过
                continue;
            }

            backtracking(s, i + 1); // 寻找i+1为起始位置的子串，切割过的位置不能重复切割，传入下一层的起始位置为i+1
            path.pop_back(); // 回溯过程，弹出本次已经在的子串
        }

    }

    bool isPalindrome(const string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

    vector<vector<string>> partition(string s) {
        backtracking(s, 0);
        return result;
    }
};

93 复原IP地址

方法1：回溯(需要再认真做)

class Solution {
private:
    vector<string> result;// 记录结果
    // startIndex: 搜索的起始位置，pointNum:添加逗点的数量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗点数量为3时，说明字符串分成了4段，分隔结束
            // 判断第四段子字符串是否合法，如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                // 如果合法就在字符串后面加上符号.表示已经分割
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2，同时记录分割符的数量pointNum要+1
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            } else break; // 不合法，直接结束本层循环
        }
    }

    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
    // 段位以0为开头的数字不合法
    // 段位里有非正整数字符不合法
    // 段位如果大于255了不合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};

40 组合总和II

方法1：回溯

class Solution {
public:

    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }

        // sum + candidates[i]<=target为剪枝操作
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target;i++) {
            // 要对同一树层使用过的元素进行跳过
            // 如果candidates[i] == candidates[i - 1]，并且i在startIndex后面，说明当前的取的candidates[i]是从candidates[i-1]回溯而来的，说明前一个树枝使用了candidates[i-1]，也就是说同一树层使用过candidates[i-1]
            // 此时for循环里就应该做continue操作
            if (i > startIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }

            sum += candidates[i];
            path.push_back(candidates[i]);
            // 每个数字在每个组合中只能使用一次，所以是i+1
            backtracking(candidates, target, sum, i + 1);
            path.pop_back();
            sum -= candidates[i];
        }
    }


    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        path.clear();
        result.clear();
        // 首先把给candidates排序，让其相同的元素都挨在一起
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

78 子集

方法1：回溯

是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
        // startIndex已经大于数组的长度了，就终止了，因为没有元素可取了
        if (startIndex >= nums.size()) {
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);    // 子集收集元素
            backtracking(nums, i + 1);  // 注意从i+1开始，元素不重复取
            path.pop_back();            // 回溯
        }
    }


    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums, 0);
        return result;
    }
};

90 子集II

方法1：回溯

主要是去重，理解“树层去重”和“树枝去重”

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            // 我们要对同一树层使用过的元素进行跳过
            // 递归的时候下一个startIndex是i+1而不是0
            // 如果nums[i] == candidates[i - 1]，并且i在startIndex后面，说明当前的取的nums[i]是从nums[i-1]回溯而来的，说明前一个树枝使用了nums[i-1]，也就是说同一树层使用过nums[i-1]
            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;
            }

            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }

    }


    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        // 需要排序
        sort(nums.begin(), nums.end());
        backtracking(nums, 0);
        return result;
    }
};

491 递增子序列

方法1：回溯

本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑！

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        if (path.size() > 1) {
            result.push_back(path);
            // 注意这里不要加return，因为要取树上的所有节点
        }

        int used[201] = { 0 }; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100
        for (int i = startIndex; i < nums.size(); i++) {
            if ((!path.empty() && nums[i] < path.back()) || used[nums[i] + 100] == 1) {
                continue;
            }

            used[nums[i] + 100] = 1; // 记录这个元素在本层用过了，本层后面不能再用了。新的一层used都会重新定义（清空），所以知道used只负责本层
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }


    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums, 0);
        return result;
    }
};

46 全排列

方法1：回溯

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    // 排列是有序的，要重复用，所以处理排列问题就不用使用startIndex
    void backtracking(vector<int>& nums, vector<bool>& used) {
        // 可以看出叶子节点，就是收割结果的地方。
        // 收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (used[i] == true) continue;  // path里已经收录的元素，直接跳过
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }


    vector<vector<int>> permute(vector<int>& nums) {
        // used标记已经选择的元素
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

第2次

class Solution {
public:
    void backtrack(vector<int>& path, const vector<int>& nums, vector<bool>& selected, vector<vector<int>>& res){
        if(path.size()==nums.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(!selected[i]){
                selected[i]=true;
                path.push_back(nums[i]);
                backtrack(path, nums, selected, res);
                path.pop_back();
                selected[i]=false;
            }
        }

    }


    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        vector<vector<int>> res;
        vector<bool> selected(nums.size());
        backtrack(path, nums, selected, res);
        return res;
    }
};

47 全排列II

方法1：回溯

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            // i目前为1，nums[i]==nums[i-1],而used[i-1]为false，说明同一树层上有两个重复的元素nums[i]和nums[i-1]，不可以重复选取

            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过 
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }

            if (used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

332 重新安排行程

方法1：回溯

在选择映射函数的时候，不能选择unordered_map<string, multiset<string>> targets， 因为一旦有元素增删multiset的迭代器就会失效

本题既要找到一个对数据进行排序的容器，而且还要容易增删元素，迭代器还不能失效。选择了unordered_map<string, map<string, int>> targets 来做机场之间的映射。

class Solution {
public:
    // unordered_map<出发机场, map<到达机场, 航班次数>> targets
    unordered_map<string, map<string, int>> targets;
    // 返回bool，只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线
    bool backtracking(int ticketNum, vector<string> & result) {
        // 遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了
        if (result.size() == ticketNum + 1) { // 记录到达机场是否飞过了
            return true;
        }

        // result记录的最后一个数，作为本次的出发机场
        for (pair<const string, int> &target : targets[result[result.size() - 1]]) {
            // 对应本次出发机场的到达机场，其航班次数大于0时
            if (target.second > 0) { 
                target.second--;
                // 存入其达到机场
                result.push_back(target.first);
                if (backtracking(ticketNum, result)) return true;
                result.pop_back();
                target.second++;
            }
        }

        return false;
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> result;
        // 把tickets映射为targets
        for (const vector<string> &vec : tickets) {
            targets[vec[0]][vec[1]]++; // 记录映射关系
        }
        result.push_back("JFK"); // 起始机场
        backtracking(tickets.size(), result);
        return result;
    }
};

51 N皇后

方法1：回溯

二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。

用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

class Solution {
public:
    vector<vector<string>> result;
    // n 为输入的棋盘大小
    // row 是当前递归到棋盘的第几行了
    // 参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了
    void backtracking(int n, int row, vector<string>& chessboard) {
        // 参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了
        if (row == n) {
            result.push_back(chessboard);
            return;
        }

        // 递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。
        // 每次都是要从新的一行的起始位置开始搜，所以都是从0开始。
        for (int col = 0; col < n; col++) { 
            if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
                chessboard[row][col] = 'Q'; // 放置皇后
                backtracking(n, row + 1, chessboard);
                chessboard[row][col] = '.'; // 回溯，撤销皇后
            }
        }

    }

    bool isValid(int row, int col, vector<string>& chessboard, int n) {
        // 检查列
        for (int i = 0; i < row; i++) { // 这是一个剪枝，只验证到当前行为止
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查 45度角是否有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查 135度角是否有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};

37 解数独

方法1：回溯

class Solution {
private:
bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {        // 遍历行
        for (int j = 0; j < board[0].size(); j++) { // 遍历列
            if (board[i][j] == '.') {
                for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适
                    if (isValid(i, j, k, board)) {
                        board[i][j] = k;                // 放置k
                        if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                        board[i][j] = '.';              // 回溯，撤销k
                    }
                }
                return false;  // 9个数都试完了，都不行，那么就返回false 
            }                
        }
    }
    return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) { // 判断行里是否重复
        if (board[row][i] == val) {
            return false;
        }
    }
    for (int j = 0; j < 9; j++) { // 判断列里是否重复
        if (board[j][col] == val) {
            return false;
        }
    }
    int startRow = (row / 3) * 3; // 会从九宫格最开始的那个数开始
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == val ) {
                return false;
            }
        }
    }
    return true;
}
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

79 单词搜索

方法1：回溯

class Solution {
public:
    // 四个方向
    int dir[4][4] = { {-1,0},{1,0},{0,-1},{0,1} };

    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, 0, board, word, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(int x, int y, int index, vector<vector<char>>& board, string word, vector<vector<bool>>& visited) {
        // 终止条件：遍历到word的最后一个，返回最后一个是否相等
        if (index == word.size() - 1) {
            return word[index] == board[x][y];
        }

        // 如果相等，去处理节点
        if (word[index] == board[x][y]) {
            // 处理当前节点置为true
            visited[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int new_x = x + dir[i][0];
                int new_y = y + dir[i][1];
                // 满足条件去进行递归
                if (new_x >= 0 && new_x < board.size() && new_y >= 0 && new_y < board[0].size() && !visited[new_x][new_y]) {
                    if (dfs(new_x, new_y, index + 1, board, word, visited)) {
                        return true;
                    }
                }
            }
            // 如果这个点的下一个点不行，重新把当前节点置为false
            // 也就是回溯撤销结果
            visited[x][y] = false;
        }
        return false;         
    }
};

方法2：K神

79. 单词搜索 - 力扣（LeetCode）

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        rows = board.size();
        cols = board[0].size();
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
private:
    int rows, cols;
    bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
        if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;
        if (k == word.size() - 1) return true;
        board[i][j] = '\0';
        bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
};

39、组合总和

39. 组合总和 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i < candidates.size(); i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i);
            path.pop_back();
            sum -= candidates[i];

        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

46、全排列

46. 全排列 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
private:
    vector<vector<int>> res;
    void dfs(vector<int> nums, int x) {
        if (x == nums.size() - 1) {
            res.push_back(nums);      // 添加排列方案
            return;  
        }
        for (int i = x; i < nums.size(); i++) {
            swap(nums[i], nums[x]);   // 交换，将 nums[i] 固定在第 x 位
            dfs(nums, x + 1);         // 开启固定第 x + 1 位元素
            swap(nums[i], nums[x]);   // 恢复交换
        }
    }
};