回溯算法题解（难度由小到大）（力扣，洛谷）

  • 开发
  • 18

目录

注意：

P1157 组合的输出（洛谷）https://www.luogu.com.cn/problem/P1157int result[10000] = { 0 };

216. 组合总和 IIIhttps://leetcode.cn/problems/combination-sum-iii/

17. 电话号码的字母组合https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

39. 组合总和https://leetcode.cn/problems/combination-sum/

40. 组合总和 IIhttps://leetcode.cn/problems/combination-sum-ii/

131. 分割回文串https://leetcode.cn/problems/palindrome-partitioning/

93. 复原 IP 地址https://leetcode.cn/problems/restore-ip-addresses/

78. 子集https://leetcode.cn/problems/subsets/

90. 子集 IIhttps://leetcode.cn/problems/subsets-ii/

491.非递减子序列

46. 全排列https://leetcode.cn/problems/permutations/

47. 全排列 IIhttps://leetcode.cn/problems/permutations-ii/

P1219 [USACO1.5] 八皇后 Checker Challengehttps://www.luogu.com.cn/problem/P1219

51. N 皇后https://leetcode.cn/problems/n-queens/

37. 解数独https://leetcode.cn/problems/sudoku-solver/

 

✨欢迎来到脑子不好的小菜鸟的文章✨

      🎈创作不易，麻烦点点赞哦🎈

          所属专栏：刷题_脑子不好的小菜鸟的博客-CSDN博客

          我的主页：脑子不好的小菜鸟

          文章特点：关键点和步骤讲解放在

          代码相应位置

注意：

本篇由易到难，若想做难题，可移步至该文章：过去一周写过的算法题的一部分（dfs，贪心）-CSDN博客

P1157 组合的输出（洛谷）
https://www.luogu.com.cn/problem/P1157int result[10000] = { 0 };


void dfs(int n, int r, int size, int start){
    int i;
    //终止条件
    if (size == r)
    {
        for (i = 0; i < size; i++)
        {
            printf("%3d", result[i]);
        }
        printf("\n");
        return;
    }
    
    //单层递归逻辑
    for (i = start; i <= n - (r - size) + 1; i++)//剪枝
    {
        result[size] = i;
        dfs(n, r, size + 1, i + 1);
    }
}
int main(){
    int n, r;
    scanf("%d%d", &n, &r);
    dfs(n, r, 0, 1);
    return 0;
}

216. 组合总和 III
https://leetcode.cn/problems/combination-sum-iii/

class Solution {
public:
    vector<vector<int>>result;
    vector<int>path;
    void backtracking(int k, int n, int sum, int start)
    {
        if (sum > n || start > n)    return;
        if (sum == n && path.size() == k)
        {
            result.push_back(path);
            return;
        }

        int i;
        for (i = start; i <= 9; i++)//可优化(剪枝)
        {
            path.push_back(i);
            if (sum + i <= n)   backtracking(k, n, sum + i, i + 1);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum3(int k, int n) 
    {
        backtracking(k, n, 0, 1);
        return result;
    }
};

17. 电话号码的字母组合
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/



//注意是组合，不是排列
//需要先将各个按键代表的字符串记录---->枚举常量

//该题注意：
//1.C++中的类似C语言中枚举的定义方式
//2.对枚举的常量的调用
class Solution {
public:
    const string/**/ lettermap[10]/**/ =/**/ {
        "",
        "",//这两行不能省，否则按0，1这两种情况解决不了
        "abc" ,
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",/**/
    };
    vector<string>result;
    string path;
    void backtracking(string digits, int index)
    {
        if (path.size() == digits.size())/**/
        {
            result.push_back(path);
            return;
        }

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

39. 组合总和
https://leetcode.cn/problems/combination-sum/



//与之前的组合问题不同的是：这需要在每一个节点判断结果，而不是叶子节点

class Solution {
public:
    vector<int>path;
    vector<vector<int>>result;
    void backtracking(vector<int>& candidates, int target, int sum, int start)
    {
        if (sum > target)   return;
        if (sum == target)
        {
            result.push_back(path);
            return;
        }
        
        int i;
        for (i = start; i < candidates.size(); i++)
        {
            path.push_back(candidates[i]);
            if (sum + candidates[i] <= target)  backtracking(candidates, target, sum + candidates[i], i/*注意是i，不是i + 1*/);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

40. 组合总和 II
https://leetcode.cn/problems/combination-sum-ii/


//map是find键，而不是值
//unordered_map<vector<int>, int>map;要自己构造哈希函数

/*！！！该题重点：不能有重复的集合----->树层去重，树枝去重
树层去重目的：不出现相同的组合（用used数组）
树枝去重目的：一个数不被用两次（用start控制起始下标）
！！！！*/

class Solution {
public:
    vector<int>path;
    vector<vector<int>>result;
    void backtracking(vector<int>& candidates, int target, int sum, int start, vector<bool>& used)
    {
        if (sum == target)
        {
            result.push_back(path);
            return;
        }
        
        int i;
        for (i = start; i < candidates.size(); i++)
        {
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false/***不是true,若为true,说明是同一树枝，而不是树层***/)
                continue;

            path.push_back(candidates[i]);
            used[i] = true;
            if (sum + candidates[i] <= target)  backtracking(candidates, target, sum + candidates[i], i + 1, used);
            used[i] = false;
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        vector<bool> used(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, used);
        return result;
    }
};

131. 分割回文串
https://leetcode.cn/problems/palindrome-partitioning/


//重点：分割字符串
//注意strsub（分割字符串）的使用：strsub(string s, 起始坐标，分割的字母个数);

class Solution {
public:
    vector<vector<string>>result;
    vector<string>str;
    bool ishuiwen(string& s, int start, int end)
    {
        int i = start, j = end;
        while (i < j)
        {
            if (s[i] != s[j])
                return false;
            
            i++;
            j--;
        }
        return true;
    }
    void backtracking(string& s, int start)
    {
        if (start >= s.size())
        {
            result.push_back(str);
            return;
        }

        int i;
        for (i = start; i < s.size(); i++)
        {
            if (ishuiwen(s, start, i))
            {
                string temp = s.substr(start, i - start + 1);
                str.push_back(temp);
                backtracking(s, i + 1);
                str.pop_back();
            }
            else
                continue;
        }
    }
    vector<vector<string>> partition(string s) 
    {
        if (s.size() == 0)  return result;
        backtracking(s, 0);
        return result;
    }
};

93. 复原 IP 地址
https://leetcode.cn/problems/restore-ip-addresses/



//该题不要path,直接在s里加'.'
//注意insert和erase的使用

class Solution {
public:
    vector<string>result;
    bool islegal(string& s, int start, int end)
    {
        if (s[start] == '0' && end - start != 0)
            return false;
        int sum = 0;
        int i;
        for (i = start; i <= end; i++)
        {
            if (s[i] < '0' && s[i] > '9')
                return false;
            
            sum = sum * 10 + (s[i] - '0');
            if (sum > 255)/******要放在for循环里面*****/
                return false;
        }
        return true;
    }
    void backtracking(string& s, int num, int start)
    {
        if (num == 3)
        {
            if (islegal(s, start, s.size() - 1))
            {
                result.push_back(s);
            }
            return;
        }

        int i;
        for (i = start; i < s.size(); i++)
        {
            if (islegal(s, start, i) && i + 1 != s.size()/*******/)
            {
                s.insert(s.begin() + i + 1, '.');
                // string temp = s.substr(start, i - start + 1);
                // path.push_back(temp);
                // path.push_back('.');
                backtracking(s, num + 1, i + 1 + 1/*注意不是i + 1*/);
                // path.pop_back();
                s.erase(s.begin() + i + 1);
            }
            else
                break;/******/
        }
    }
    vector<string> restoreIpAddresses(string s) 
    {
        if (s.size() < 4 || s.size() > 12)
            return result;
        
        backtracking(s, 0, 0);
        return result;
    }
};

78. 子集
https://leetcode.cn/problems/subsets/



class Solution {
public:
    vector<vector<int>>result;
    vector<int>path;
    void backtracking(vector<int>& nums, int start)
    {
        result.push_back(path);

        int i;
        for (i = start; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        backtracking(nums, 0);
        return result;
    }
};

90. 子集 II
https://leetcode.cn/problems/subsets-ii/



//注意点：解集 不能 包含重复的子集------>涉及树层的去重问题

class Solution {
public:
    vector<int>path;
    vector<vector<int>>result;
    void backtracking(vector<int>& nums, vector<int>& used, int start)
    {
        result.push_back(path);
        
        int i;
        for (i = start; i < nums.size(); i++)
        {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)/*树层去重的关键*/
                continue;
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, used, i + 1);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());/*树层去重的关键！！！！！！！！！！！*/
        vector<int>used(nums.size(), false);
        backtracking(nums, used, 0);
        return result;
    }
};

491.非递减子序列

注意：
放入答案时要注意其大小和path中最后一个元素的大小，注意是path的最后一个，而不是数组的前一个
https://leetcode.cn/problems/non-decreasing-subsequences/



//注意unordered_set的使用，与map不同，加入是insert,查找不可用下标
//注意查看vector的最后一个元素不可用下标，而是vector.back()


class Solution {
public:
    vector<int>path;
    vector<vector<int>>result;
    void backtracking(vector<int>& nums/*, vector<int>& used*/, int start)
    {
        if (path.size() >= 2)
            result.push_back(path);

        unordered_set<int>uset;/**!!!!!!!!!!!!!!!!!!*/
        
        int i;
        for (i = start; i < nums.size(); i++)
        {
            /*注意使用path.back()时要检查path是否为空*/
            if (!path.empty() && nums[i] < path.back())
                continue;

            /*[10,1,1,1,1,1]过不了，因为这题没有排序，而是按照之前的顺序，因此比较nums[i]和nums[i-1]没用*/
            // if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)/*树层去重的关键*/
            //     continue;

            if (uset.find(nums[i]) != uset.end())/*树层去重的关键*/
                continue;
                
            path.push_back(nums[i]);
            uset.insert(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
            // uset[nums[i]] = 0;(不用,因为退出该层就重新创建了)
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) 
    {
        // vector<int>used(nums.size(), false);
        // backtracking(nums, used, 0);

        backtracking(nums, 0);
        return result;
    }
};

46. 全排列
https://leetcode.cn/problems/permutations/



class Solution {
public:
    vector<int>path;
    vector<vector<int>>result;
    void backtracking(vector<int>& nums, vector<int>& used)
    {
        if (path.size() == nums.size())
        {
            result.push_back(path);
            return;
        }

        int i;
        for (i = 0; i < nums.size(); i++)
        {
            if (used[i] == 1)
                continue;
            path.push_back(nums[i]);
            used[i] = 1;
            backtracking(nums, used);
            path.pop_back();
            used[i] = 0;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) 
    {
        if (nums.size() == 0)
            return result;
        vector<int> used(nums.size(), 0);/*一定要初始化*/
        backtracking(nums, used);
        return result;
    }
};

47. 全排列 II
https://leetcode.cn/problems/permutations-ii/



//又涉及树层去重

class Solution {
public:
    vector<int>path;
    vector<vector<int>>result;
    void backtracking(vector<int>& nums, vector<int>& used)
    {
        if (path.size() == nums.size())
        {
            result.push_back(path);
            return;
        }

        int i;
        for (i = 0; i < nums.size(); i++)
        {
            if (i > 0 && nums[i] == nums[i-1] && used[i - 1] == 0)
                continue;

            if (used[i] == 1)/*不能少*/
                continue;

            path.push_back(nums[i]);
            used[i] = 1;
            backtracking(nums, used);
            path.pop_back();
            used[i] = 0;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        if (nums.size() == 0)
            return result;
        
        sort(nums.begin(),nums.end());
        vector<int> used(nums.size(), 0);/*一定要初始化*/
        backtracking(nums, used);
        return result;
    }
};

P1219 [USACO1.5] 八皇后 Checker Challenge
https://www.luogu.com.cn/problem/P1219



int count = 0, ans[50] = { 0 }, lie[50] = { 0 }, dui[50] = { 0 }, fandui[17] = { 0 };
void dfs(int n, int row)
{
	int i;
	if (row == n + 1)/*注意是n + 1啊*/
	{
		count++;
		if (count <= 3)
		{
			for (i = 0; i < n; i++)
				printf("%d ", ans[i]);
			printf("\n");
		}
		return;
	}

	for (i = 1; i <= n; i++)//列
	{
		if (lie[i] == 1 || dui[i + row] == 1 || fandui[i - row + n] == 1)
			continue;

		lie[i] = 1;
		dui[i + row] = 1;
		fandui[i - row + n] = 1;

		ans[row - 1] = i;
		dfs(n, row + 1);

		lie[i] = 0;
		dui[i + row] = 0;
		fandui[i - row + n] = 0;
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	dfs(n, 1);
	printf("%d\n", count);
	return 0;
}

51. N 皇后
https://leetcode.cn/problems/n-queens/



//注意主对角线和副对角线的行列之间的关系

/*
<0,0>  <0,1>  <0,2>
 
<1,0>  <1,1>  <1,2>
 
<2,0>  <2,1>  <2,2>
*/

//主对角线：y - x相等------>注意可能是负数：至少要加上n - 1---->可能和主对角线的标记重复----->都加上n - 1
//副      ：y + x相等

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

        int i, j;
        for (j = 0; j < n; j++)
        {
            if (isValid(size, j, n,path))
            {
                path[size][j] = 'Q';
                backtracking(n, size + 1,path);
                path[size][j] = '.';
            }
        }
        
    }
    vector<vector<string>> solveNQueens(int n) 
    {
        //表示的是：path是一个装满string的容器，容器被初始化为有n个元素，每个元素是string，string被初始化为长度为n的.
        //：：是一个作用域解析运算符，用于指定一个名称在哪个命名空间或类中定义的
        //std ---->using namespace std;//用了叫做std的命名空间
        std::vector<std::string> path(n, std::string(n, '.'));/*先全部初始化为'.'*/
        backtracking(n, 0, path);
        return res;
    }
};

37. 解数独
https://leetcode.cn/problems/sudoku-solver/


class Solution {
public:
    bool isValid(vector<vector<char>>& board, int row, int col, char ch)
    {
        int i, j;
        for (i = 0; i < board.size(); i++)
        {
            for (j = 0; j < board[0].size(); j++)
            {
                if (i == row && board[i][j] == ch)
                    return false;
                
                if (j == col && board[i][j] == ch)
                    return false;

            }
        }
        
        int startx = row / 3 * 3;
        int starty = col / 3 * 3;
        for (i = startx; i < startx + 3; i++)
        {
            for (j = starty; j < starty + 3; j++)
            {
                if (board[i][j] >= '1' && board[i][j] <= '9' && board[i][j] == ch)
                    return false;
            }
        }
        return true;
    }
    //该题没有终止条件也没事，因为两层循环进行完了就会结束
    bool backtracking(vector<vector<char>>& board)
    {
        int i, j;
        for (i = 0; i < board.size(); i++)
        {
            for (j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] <= '9' && board[i][j] >= '1')
                    continue;
                
                for (char ch = '1'; ch <= '9'; ch++)
                {
                    if (isValid(board, i, j, ch))
                    {
                        board[i][j] = ch;
                        if(backtracking(board))/*只要一种结果---->找到就立马返回---->递归函数要有返回值*/
                            return true;
                        board[i][j] = '.';
                    }
                }
                return false;//9个数都试完了，都没找到
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) 
    {
        backtracking(board);
    }

看完了记得关注我哦：脑子不好的小菜鸟

以后共同进步，该账号会发布项目，算法，知识点等内容

阅读全部

相关推荐

  6. 洛谷P1234题解

    2024-03-11 18:42:02       13 阅读

  7. 洛谷P10397题解

    2024-03-11 18:42:02       14 阅读

  8. 回溯算法经典题目洛谷题目解析：P1219（n皇后问题）、P1135、P1036、P1443、P1605

    2024-03-11 18:42:02       11 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-03-11 18:42:02       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-03-11 18:42:02       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-03-11 18:42:02       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-03-11 18:42:02       20 阅读

热门阅读

  1. uniapp聊天页面之消息滚动

    2024-03-11 18:42:02       20 阅读

  2. 大数据开发（Hadoop面试真题-卷九）

    2024-03-11 18:42:02       22 阅读

  5. LeetCode104 二叉树的最大深度

    2024-03-11 18:42:02       19 阅读

  8. 01.AJAX 概念和 axios 使用

    2024-03-11 18:42:02       22 阅读

  9. Spring中SmartInitializingSingleton、SmartLifecycle和Lifecycle的作用和区别

    2024-03-11 18:42:02       20 阅读

  14. K8S Service

    2024-03-11 18:42:02       25 阅读

  15. Linux进程初步理解

    2024-03-11 18:42:02       25 阅读

  16. SpringBoot中事务

    2024-03-11 18:42:02       26 阅读

  18. Android10禁用wifi随机mac地址，固定mac地址

    2024-03-11 18:42:02       21 阅读

  19. 小蓝的钥匙（蓝桥杯错排）

    2024-03-11 18:42:02       24 阅读

  20. JDBC编程(数据库编程)

    2024-03-11 18:42:02       22 阅读

  21. 视觉信息处理和FPGA实现第二次作业

    2024-03-11 18:42:02       23 阅读

  22. 获取webshell的十种方法

    2024-03-11 18:42:02       20 阅读

  27. Docker与低代码开发：重塑软件开发的未来

    2024-03-11 18:42:02       21 阅读