491.递增子序列, 46.全排列, 47.全排列 II

简介: **简介:**本文介绍了三道经典的回溯算法题目及其解法,分别是“491. 递增子序列”、“46. 全排列”和“47. 全排列 II”。其中,“491”要求从数组中找出所有不同的递增子序列,需注意去重且不能对原数组排序;“46”是求不含重复数字数组的所有全排列,使用布尔数组记录元素使用状态;“47”则针对含重复数字的数组求不重复的全排列,通过排序与树层去重实现。这些题目涵盖了回溯算法中的常见问题类型,如子集、排列以及去重处理,帮助读者深入理解回溯算法的核心思想与实现细节。代码示例详细展示了如何通过递归与剪枝优化解决问题,是学习回溯算法的经典案例。

题目:491. 递增子序列

给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。

示例 1:

输入:nums = [4,6,7,7]

输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2:

输入:nums = [4,4,3,2,1]

输出:[[4,4]]

提示:

1 <= nums.length <= 15

-100 <= nums[i] <= 100

思考历程与知识点:  

这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。

这又是子集,又是去重,是不是不由自主的想起了刚刚讲过的90.子集II (opens new window)。

就是因为太像了,更要注意差别所在,要不就掉坑里了!

在90.子集II (opens new window)中我们是通过排序,再加一个标记数组来达到去重的目的。

而本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子序列了。

所以不能使用之前的去重逻辑。

题解:

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        if (path.size() > 1) {
            result.push_back(path);
            // 注意这里不要加return,要取树上的节点
        }
        unordered_set<int> uset; // 使用set对本层元素进行去重
        for (int i = startIndex; i < nums.size(); i++) {
            if ((!path.empty() && 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();
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

 题目:46. 全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]

输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入:nums = [0,1]

输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]

输出:[[1]]

提示:

1 <= nums.length <= 6

-10 <= nums[i] <= 10

nums 中的所有整数 互不相同

思考历程与知识点:  

因为排列问题,每次都要从头开始搜索,例如元素1在[1,2]中已经使用过了,但是在[2,1]中还要再使用一次1。

而used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次。

题解:

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++) {
            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) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

 题目:47. 全排列 II

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

示例 1:

输入:nums = [1,1,2]

输出:

[[1,1,2],

[1,2,1],

[2,1,1]]

示例 2:

输入:nums = [1,2,3]

输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示:

1 <= nums.length <= 8

-10 <= nums[i] <= 10

题解:

class Solution {
private:
    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++) {
            // 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;
            }
        }
    }
public:
    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;
    }
};


相关文章
|
安全 数据处理 C++
【Qt 底层之事件驱动系统】深入理解 Qt 事件机制:主事件循环与工作线程的交互探究,包括 QML 的视角
【Qt 底层之事件驱动系统】深入理解 Qt 事件机制:主事件循环与工作线程的交互探究,包括 QML 的视角
3881 3
原理篇:Seata TCC模式是如何解决幂等性、资源悬挂、空回滚问题的
原理篇:Seata TCC模式是如何解决幂等性、资源悬挂、空回滚问题的
2074 0
|
iOS开发 芯片 MacOS
macOS Tahoe 26.4.1 (25E253) 正式版 ISO、IPSW、PKG 下载
2026 年 4 月 10 日凌晨,macOS Tahoe 26.4.1 (25E253) 发布,此为安全更新。
1204 0
|
Shell 开发工具 数据安全/隐私保护
解决git clone与git push出现的若干问题:Failed to connect to github.com port 443: Timed out
解决git clone与git push出现的若干问题:Failed to connect to github.com port 443: Timed out
9106 1
解决git clone与git push出现的若干问题:Failed to connect to github.com port 443: Timed out
|
10月前
|
弹性计算 人工智能 小程序
2026阿里云服务器最新价格大全:ECS、轻量、GPU 高性价比套餐汇总
2026年阿里云推出轻量服务器38元/年起、ECS 99元/年起、GPU服务器4折起等优惠,覆盖个人开发者至企业全场景需求,新老用户同享,续费同价,助力低成本上云。
|
缓存 异构计算
LLM 内存需求计算方式
GPU上大语言模型的内存主要由模型权重和KV缓存构成。70亿参数模型以16位精度加载时,权重占约14GB;KV缓存则随批大小和序列长度线性增长,显著影响显存使用,限制推理吞吐与长上下文处理。
1298 11
|
11月前
|
机器学习/深度学习 存储 知识图谱
知识蒸馏
知识蒸馏是一种模型压缩技术,通过将大模型(教师)的知识迁移到小模型(学生)中,在降低计算成本的同时提升小模型性能。核心思想是让学生模仿教师的输出分布或中间特征。常用方法包括基于软标签的Hinton蒸馏(引入温度提升泛化信息)、特征蒸馏(对齐中间层表示)。按信息访问程度分为黑盒(仅输出)与白盒(含内部结构)。广泛用于加速推理与模型轻量化。
551 0
|
人工智能
技术心得记录:关于自补图的认识和构造(无证明)
技术心得记录:关于自补图的认识和构造(无证明)
1139 0
|
SQL Oracle 关系型数据库
《深度剖析:MySQL、Oracle、SQL Server分页语法大揭秘》
分页查询是数据处理中的核心技术,尤其在海量数据场景下至关重要。本文深入解析了MySQL、Oracle和SQL Server三大主流数据库的分页语法及其特点。MySQL以简洁直观的LIMIT语法见长,适合中小规模数据;Oracle通过ROWNUM及新引入的OFFSET/FETCH实现复杂灵活的分页;SQL Server自2012版起支持OFFSET/FETCH,性能高效且扩展性强。开发者需根据项目数据量、业务需求及数据库版本选择合适的分页方案,以优化查询效率和用户体验。掌握这些技术,可为高效数据展示奠定坚实基础。
590 1
|
JavaScript 前端开发 数据管理
使用Sortable.js库 实现Vue3 elementPlus 的 el-table 拖拽排序
使用Sortable.js库 实现Vue3 elementPlus 的 el-table 拖拽排序
5160 1