代码随想录笔记---回溯篇

回溯模板

void backtracking(参数)
{
	if(终止条件)
	{
		存放结果;
		return;
	}
	
	for (选择:本层集合中的元素（树中节点孩子的数量就是集合的大小）)
	{
		处理节点;
		backtracking(路径，选择列表); // 递归
		回溯,撤销处理结果;
	}
}

一、2025.4.26

1. 学习内容

77. 组合

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) {
        backtracking(n, k, 1);
        return result;
    }

77.组合(优化)

vector<vector<int>> result;
    vector<int> path;

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

        //进行剪枝的关键在于:列表中的剩余元素(n - i + 1) >= path数组需要存储的剩余数量 (k - path.size()),
        //进而得到了i <= n - (k - path.size()) + 1;
        for (int i = startIndex; 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) {
        backtracking(n, k, 1);
        return result;
    }

2.复习内容

707. 设计链表

class MyLinkedList {

public:
    struct LinkedNode
    {
        int val;
        LinkedNode* next;
        LinkedNode(int x):val(x), next(nullptr){}
    };

    MyLinkedList() {
        dummy_Head = new LinkedNode(0);
        _size = 0;
    }
    
    int get(int index) {
        if (index > (_size - 1) || index < 0) return -1;
        LinkedNode* cur = dummy_Head -> next;
        while (index--)
        {
            cur = cur -> next;
        }
        return cur -> val;
    }
    
    void addAtHead(int val) {
        LinkedNode* node = new LinkedNode(val);
        node -> next = dummy_Head -> next;
        dummy_Head -> next = node;
        _size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* cur = dummy_Head;
        while (cur -> next)
        {
            cur = cur -> next;
        }
        LinkedNode* node = new LinkedNode(val);
        cur -> next = node;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index > _size) return;
        if (index < 0) index = 0;
        LinkedNode* cur = dummy_Head;
        while (index--)
        {
            cur = cur -> next;
        }
        LinkedNode* node = new LinkedNode(val);
        node -> next = cur -> next;
        cur -> next = node;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if (index < -1 || index > (_size - 1)) return;
        LinkedNode* cur = dummy_Head;
        while (index--)
        {
            cur = cur -> next;
        }
        LinkedNode* tmp = cur -> next;
        cur -> next = cur -> next -> next;
        delete tmp;
        _size--;
    }

private:
    int _size;
    LinkedNode* dummy_Head;
};

206. 反转链表

ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr, * cur = head, *tmp = nullptr;
        while (cur)
        {
            tmp = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

2025.5.1

1.学习内容

17. 电话号码的字母组合

const string letterMap[10] = 
    {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };

    string path = "";
    vector<string> result;

    void backtracking(string digits, int index)
    {
        if (index == digits.size())
        {
            result.push_back(path);
            return;
        }
        
        int digit = digits[index] - '0';
        for (int i = 0; i < letterMap[digit].size(); i++)
        {
            string letter = letterMap[digit];
            path.push_back(letter[i]);
            backtracking(digits, index + 1);
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        path.clear();
        result.clear();
        if (digits.size() == 0) return result;
        backtracking(digits, 0);
        return result;
    }

2.复习内容

216.组合总和III

vector<int> path;
    vector<vector<int>> result;

    void back_tracking(int startIndex, int sum, int n, int k)
    {
        if (path.size() == k)
        {
            if (sum == n) result.push_back(path);
            return;
        }
        if (sum >= n) return; 
        //k - path.size() <= 9 - i + 1;
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++)
        {
            path.push_back(i);
            sum += i;
            //记住回溯的条件选择:是i+1,而不是startIndex + 1
            back_tracking(i + 1, sum, n, k);
            sum -= i;
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        path.clear();
        result.clear();
        back_tracking(1, 0, n, k);
        return result;
    }

2025.5.2

1.学习内容

39. 组合总和

vector<int> path;
    vector<vector<int>> result;

    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++)
        {
            path.push_back(candidates[i]);
            sum += candidates[i];
            //相比于组合,这块应该是i + 1
            backtracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();
        }
    }

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

40. 组合总和 II

vector<int> path;
    vector<vector<int>> result;

    void backtracking(vector<int> candidates, int target, int sum, int startIndex, vector<bool> &used)
    {
        if (sum > target) return;
        if (sum == target)
        {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size(); i++)
        {
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) continue;
            path.push_back(candidates[i]);
            sum += candidates[i];
            used[i] = true;
            backtracking(candidates, target, sum, i + 1, used);
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        path.clear();
        result.clear();
        //感觉要将candidates数组进行排序
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, used);
        return result;
    }

2025.5.7

1.学习内容

90. 子集 II

//子集问题就是要保存树的所有节点
    vector<int> path;
    vector<vector<int>> result;

    void backtracking(vector<int> nums, int startIndex, vector<bool>& used)
    {
        //直接将节点存储到result中
        result.push_back(path);
        //省略终止条件,因为for循环结束后会自动终止

        for (int i = startIndex; i < nums.size(); i++)
        {
            //used[i] == false应该就是树层去重
            if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) continue;
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            used[i] = false;
            path.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        path.clear();
        result.clear();
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtracking(nums, 0, used);
        return result;
    }

491.递增子序列

//使用哈希表
vector<int> path;
    vector<vector<int>> result;

    void backtracking(vector<int> nums, int startIndex)
    {
        if (path.size() > 1) result.push_back(path);

        unordered_set<int> uset;
        for (int i = startIndex; i < nums.size(); i++)
        {
            //排除情况: 1.不是递增; 2.在该层已经使用过了num[i]元素
            if ((path.size() > 0 && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()) continue;
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

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

使用数组代替字典
vector<int> path;
    vector<vector<int>> result;

    void backtracking(vector<int> nums, int startIndex)
    {
        if (path.size() > 1) result.push_back(path);

        //由于-100 < nums[i] < 100,使用数组代替字典
        int uset[201] = {0};
        for (int i = startIndex; i < nums.size(); i++)
        {
            //排除情况: 1.不是递增; 2.在该层已经使用过了num[i]元素
            if ((path.size() > 0 && nums[i] < path.back()) || uset[nums[i] + 100] == 1) continue;

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

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

46. 全排列

vector<int> path;
    vector<vector<int>> result;

    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++)
        {
            if (used[i] == true) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        path.clear();
        result.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }

47. 全排列 II

vector<int> path;
    vector<vector<int>> result;

    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++)
        {
            //一定要好好区分是树枝上去重还是树层上去重
            if (used[i] == true || (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false)) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        path.clear();
        result.clear();
        vector<bool> used(nums.size(), false);
        //去重一定要对元素进行排序
        sort(nums.begin(), nums.end());
        backtracking(nums, used);
        return result;
    }

2.复习内容

78. 子集

vector<int> path;
    vector<vector<int>> result;

    void backtracking(vector<int> nums, int startIndex)
    {
        result.push_back(path);
        //这个终止条件可有可无
        if (startIndex >= nums.size()) return;
        for (int i = startIndex; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

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

93. 复原 IP 地址

vector<string> result;

    bool isValid(string s, int start, int end)
    {
        if (start > end) return false;
        if (s[start] == '0' && start != end) return false;
        int num = 0;
        for (int i = start; i <= end; i++)
        {
            if (s[i] < '0' && s[i] > '9') return false;
            num = num * 10 + (s[i] - '0');
            if (num > 255) return false;
        }
        return true;
    }

    void backtracking(string& s, int startIndex, int pointNum)
    {
        if (pointNum == 3)
        {
            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))
            {
                s.insert(s.begin() + i + 1, '.');
                pointNum++;
                backtracking(s, i + 2, pointNum);
                pointNum--;
                s.erase(s.begin() + i + 1);
            }
        }
    }

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

24. 两两交换链表中的节点

ListNode* swapPairs(ListNode* head) {
        ListNode* dummu_Head = new ListNode(0);
        dummu_Head -> next = head;
        ListNode* cur = dummu_Head;
        while (cur -> next != nullptr && cur -> next -> next != nullptr)
        {
            ListNode* tmp = cur -> next;
            ListNode* tmp1 = cur -> next -> next -> next;

            cur -> next = cur -> next -> next;
            cur -> next -> next = tmp;
            cur -> next -> next -> next = tmp1;

            cur = tmp;
        }
        head = dummu_Head -> next;
        return head;
    }

2025.5.11

1.学习内容

332. 重新安排行程

//Hierholzer 算法，我感觉和卡哥的思想很类似，但是该算法的思想有点难理解
unordered_map<string, priority_queue<string, vector<string>, std::greater<string>>> umap;

    vector<string> result;

    void dfs(string curr)
    {
        while (umap.count(curr) && umap[curr].size() > 0)
        {
            string tmp = umap[curr].top();
            umap[curr].pop();
            dfs(tmp);
        }
        result.push_back(curr);
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto &it : tickets)
        {
            umap[it[0]].push(it[1]);
        }
        dfs("JFK");

        reverse(result.begin(), result.end());
        return result;
    }

51. N 皇后

vector<vector<string>> result;

    void dfs(int n, int row, vector<string>& chessboard, vector<bool> & col, vector<bool>& dp, vector<bool>& udp)
    {
        if (row == n)
        {
            result.push_back(chessboard);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if (col[i] && dp[row + i] && udp[n - row + i])
            {
                col[i] = dp[row + i] = udp[n - row +　i] = false;
                chessboard[row][i] = 'Q';
                dfs(n, row + 1, chessboard, col, dp, udp);
                chessboard[row][i] = '.';
                col[i] = dp[row + i] = udp[n - row +　i] = true;
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n, string(n, '.'));
        vector<bool> col(n, true), dp(2 * n, true), udp(2 * n, true);
        result.clear();
        dfs(n, 0, chessboard, col, dp, udp);
        return result;
    }

37. 解数独

//一定要使用实参（&），否则的话会创建大量副本，导致超时
    bool isValid(vector<vector<char>>& board, int row, int col, char c)
    {
        //横向是否合适
        for (int i = 0; i < 9; i++)
        {
            if (board[row][i] == c) return false;
        }
        //纵向是否合适
        for (int j = 0; j < 9; j++)
        {
            if (board[j][col] == c) return false;
        }
        //九宫格内是否合适
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++)
        {
            for (int j = startCol; j < startCol + 3; j++)
            {
                if (board[i][j] == c) return false;
            }
        }
        return true;
    }

    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 c = '1'; c <= '9'; c++)
                    {
                        if (isValid(board, i, j, c))
                        {
                            board[i][j] = c;
                            if (backtracking(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    //9个数试完没有返回true，那就是false
                    return false;
                }
            }
        }
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }

70. 爬楼梯

//动态规划
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        if (n == 1) return 1;
        if (n == 2) return 2;
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }

//递归思路，但是当n大于40时会有明显的卡顿
int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }