回溯算法

77. 组合

力扣题目链接(opens new window)

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(int n, int k, int start) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }

        for (int i = start; i <= n - (k - path.size()) + 1; 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;
    }
};

216. 组合总和 III

力扣题目链接(opens new window)

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1-9 的正整数，并且每种组合中不存在重复的数字。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(int k, int n, int left) {
        if (k == 1 && n <= 9) { // n >= left
            path.push_back(n);
            result.push_back(path);
            path.pop_back();
            return;
        }
        for (int i = left; i <= 9; i++) {\
            if ((2 * (i + 1) + k - 2) * (k - 1) / 2 > n - i) {
                return;
            }
            path.push_back(i);
            backtracking(k - 1, n - i, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear();
        path.clear();

        backtracking(k, n, 1);
        return result;
    }
};

17. 电话号码的字母组合

力扣题目链接(opens new window)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

class Solution {
public:
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
    vector<string> result;
    string s;
    void backtracking(string& digits, int index) {
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        for (auto c : letterMap[digits[index] - '0']) {
            s.push_back(c);
            backtracking(digits, index + 1);
            s.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        result.clear();
        s.clear();
        if (digits.empty()) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};

39. 组合总和

力扣题目链接(opens new window)

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(vector<int>& candidates, int target, int start) {
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > target) {
                return;
            }
            if (candidates[i] == target) {
                path.push_back(candidates[i]);
                result.push_back(path);
                path.pop_back();
                return;
            }
            // candidates[i] < target
            path.push_back(candidates[i]);
            backtracking(candidates, target - candidates[i], i);
            path.pop_back();
        }
    }

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

        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0);
        return result;
    }
};

46. 全排列

力扣题目链接(opens new window)

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

class Solution {
public:
    vector<vector<int>> result;

    void backtracking(vector<int>& nums,int index) {
        if (index == nums.size()) {
            result.push_back(nums);
            return;
        }
        for (int i = index; i < nums.size(); i++) {
            swap(nums[i], nums[index]);
            backtracking(nums, index+1);
            swap(nums[i], nums[index]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        backtracking(nums, 0);
        return result;
    }
};

40. 组合总和 II

力扣题目链接(opens new window)

给定一个数组  candidates  和一个目标数  target ，找出  candidates  中所有可以使数字和为  target  的组合。

candidates  中的每个数字在每个组合中只能使用一次。

说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

集合内可以重复元素但不能有重复集合，比较复杂

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(vector<int>& candidates, int target, int start) {
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] == target) {
                path.push_back(candidates[i]);
                result.push_back(path);
                path.pop_back();
                return;
            }
            if (candidates[i] > target) {
                return;
            }
            path.push_back(candidates[i]);
            backtracking(candidates, target - candidates[i], i + 1);
            path.pop_back();
            while (i + 1 < candidates.size() && candidates[i] == candidates[i + 1]) {
                // 去重
                i++;
            }
        }
    }

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

131. 分割回文串

力扣题目链接(opens new window)

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

回溯算法 + 动态规划，还有一种记忆化搜索的方式

class Solution {
public:
    vector<vector<string>> result;
    vector<vector<bool>> isPalindrome;
    vector<string> path;

    void computePalindrome(string& s) {
        isPalindrome.resize(s.size(), vector<bool>(s.size(), false));
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (j == i) {
                    isPalindrome[i][j] = true;
                } else if (j - i == 1) {
                    isPalindrome[i][j] = s[i] == s[j];
                } else {
                    isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i+1][j-1];
                }
            }
        }
    }

    void backtracking(string& s, int start) {
        if (start == s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = start; i < s.size(); i++) {
            if (isPalindrome[start][i]) {
                string str = s.substr(start, i - start + 1);
                path.push_back(str);
                backtracking(s, i + 1);
                path.pop_back();
            }
        }
    }

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

93. 复原 IP 地址

力扣题目链接(opens new window)

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 字符串的操作真是容易忘记
• 代码随想录的答案剪枝感觉很好

class Solution {
private:
    vector<string> result;

    void backtracking(string& s, int stops, int start) {
        if (stops == 3) {
            if (isVaild(s, start, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = start; i < s.size(); i++) {
            if (isVaild(s, start, i)) {
                s.insert(s.begin() + i + 1, '.');
                backtracking(s, stops + 1, i + 2);
                s.erase(s.begin() + i + 1);
            } else {
                break;
            }
        }
    }

    bool isVaild(const string& s, int left, int right) {
        if (left > right) {
            return false;
        }
        if (s[left] == '0' && right > left) {
            // leading zero
            return false;
        }
        int num = 0;
        for (int i = left; i <= right; i++) {
            int n = s[i] - '0';
            if (n < 0 || n > 9) {
                return false;
            }
            num *= 10;
            num += n;
            if (num > 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;
    }
};

78. 子集

力扣题目链接(opens new window)

给定一组不含重复元素的整数数组  nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(const vector<int>& nums, int start) {
        result.push_back(path);
        if (start == nums.size()) {
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i+1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

90. 子集 II

力扣题目链接(opens new window)

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

同一树层上重复取 2 就要过滤掉，同一树枝上就可以重复取 2

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int start) {
        result.push_back(path);
        if (start == nums.size()) {
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            if (i > start && 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) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end());
        backtracking(nums, 0);
        return result;
    }
};

491. 递增子序列

力扣题目链接(opens new window)

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是 2。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int start) {
        if (path.size() > 1) {
            result.push_back(path);
        }
        int used[201] = {0};
        for (int i = start; i < nums.size(); i++) {
            if ((!path.empty() && nums[i] < path.back()) || used[nums[i] + 100] == 1) {
                continue;
            }
            used[nums[i] + 100] = 1;
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

47. 全排列 II

力扣题目链接(opens new window)

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

重点聊聊 i > 0 && nums[i] == nums[i - 1] && !used[i - 1] 这个条件：每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used;
    void backtracking(vector<int>& nums) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            if (!used[i]) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums);
                path.pop_back();
                used[i] = false;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        sort(nums.begin(), nums.end());
        used.resize(nums.size(), false);
        backtracking(nums);
        return result;
    }
};

332. 重新安排行程

力扣题目链接(opens new window)

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

好难，好像还可以利用入度和出度剪枝

class Solution {
private:
    unordered_map<string, map<string, int>> targets;
    bool backtracking(int ticketSize, vector<string>& result) {
        if (result.size() - 1 == ticketSize) {
            return true;
        }
        for (pair<const string, int>& target : targets[result.back()]) {
            if (target.second > 0) {
                result.push_back(target.first);
                target.second--;
                if (backtracking(ticketSize, result)) {
                    return true;
                }
                target.second++;
                result.pop_back();
            }
        }
        return false;
    }
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> result;
        for (const auto ticket : tickets) {
            targets[ticket[0]][ticket[1]]++;
        }
        result.push_back("JFK");
        backtracking(tickets.size(), result);
        return result;
    }
};

51. N 皇后

力扣题目链接(opens new window)

n  皇后问题 研究的是如何将 n  个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的  n  皇后问题 的解决方案。

class Solution {
public:
    vector<vector<string>> result;
    vector<string> path;
    void backtracking(int total, int row) {
        if (row == total) {
            result.push_back(path);
            return;
        }
        for (int col = 0; col < total; col++) {
            if (isValid(total, row, col)) {
                path[row][col] = 'Q';
                backtracking(total, row + 1);
                path[row][col] = '.';
            }
        }
    }
    bool isValid(int total, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (path[i][col] == 'Q') {
                return false;
            }
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (path[i][j] == 'Q') {
                return false;
            }
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < total; i--, j++) {
            if (path[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        path.resize(n, string(n, '.'));
        backtracking(n, 0);
        return result;
    }
};

37. 解数独

力扣题目链接(opens new window)

编写一个程序，通过填充空格来解决数独问题。

class Solution {
public:
    bool backtracking(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        if (isValid(board, i, j, k)) {
                            board[i][j] = k;
                            if (backtracking(board)) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    bool isValid(vector<vector<char>>& board, int row, int col, int num) {
        // row
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num) {
                return false;
            }
        }
        // col
        for (int j = 0; j < 9; j++) {
            if (board[j][col] == num) {
                return false;
            }
        }
        // square
        int x = (int)(row / 3) * 3;
        int y = (int)(col / 3) * 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[x + i][y + j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};