当前位置：首页 > article >正文

代码随想录DAY25 - 回溯算法 - 08/24

article 2025/3/6 11:23:16

非递减子序列

题干

思路和代码

递归法

递归优化

全排列

题干

思路和代码

递归法

全排列Ⅱ

题干

思路和代码

方法一：用集合 set 去重

方法二：先排序，再用数组去重

非递减子序列

题干

题目：给你一个整数数组 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]]

说明:

给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

注意：原数组 nums 不一定有序！

链接：. - 力扣（LeetCode）

思路和代码

这道题可以在整数数组中找子集的基础上进行调整，我们可以先找出子集大小大于等于 2 的所有子集，若子集满足非递减序列，则插入结果中。同时，数组中可能含有重复元素，因此我们需要进行去重。和之前的去重操作类似，我们需要在树层去重，而不是树枝去重，即在同一层 for 循环中进行去重，而不是对递归去重。注意：我们不可以对数组 nums 进行排序，不然会改变元素的顺序，求出的递增子序列也不同。

递归法

递归参数和返回值：参数是传入的整数数组和本层递归的起始位置 startIndex，无返回值。
递归结束条件：当遍历完整个数组则返回，写不写终止条件都可以。
递归顺序：先判断当前元素是否满足递增序列，且是否不和之前的元素重复，若满足递增且不重复，则继续递归后续的整数数组寻找递增子序列。

class Solution {
public:
    vector<int> composition;
    vector<vector<int>> result;
    void backTracking(vector<int> &nums, int startIndex){
        if (composition.size() >= 2) result.push_back(composition); // 子集大小大于等于2，才插入结果
		// 写不写终止条件都可以
        unordered_set<int> usedValue; // !!!记录在同一层 for 循环中使用过的 Value
        for (int i = startIndex; i < nums.size(); ++i) {
            if (!composition.empty() && nums[i] < composition.back()){ // 违反递增顺序，continue
                continue; // 因为后续可能还有元素，所以并不 return，而是 continue
            }
            if (usedValue.find(nums[i]) != usedValue.end()) continue; // 去重！
            composition.push_back(nums[i]);
            usedValue.insert(nums[i]); // 插入遍历过的元素
            backTracking(nums,i+1);
            composition.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backTracking(nums,0);
        return result;
    }
};

递归优化

我们在上一个方法中，用了 unordered_map 来记录遍历过的元素，程序运行的时候对 unordered_set 频繁的insert，相对费时间。而本题中数组的元素范围是[-100,100]，范围并不大，因此可以用数组直接做哈希映射，效率会提高。

设定一个大小为 201 的 bool 型数组，下标为 0~200，元素 -100 映射到下标为0的数组空间中，元素 100 映射到下标为200的数组空间。

class Solution {
public:
    vector<int> composition;
    vector<vector<int>> result;
    void backTrack(vector<int> &nums, int startIndex){
        if (composition.size() >= 2) result.push_back(composition);
        // 终止条件写不写都行
        bool isUsed[201] = {false}; // 记录元素在同一层 for 循环是否被使用过，初始化为 false
        for (int i = startIndex; i < nums.size(); ++i) {
            if (!composition.empty() && nums[i] < composition.back()) continue;
            if (isUsed[nums[i]+100]) continue; // 若被使用过，则去重，跳过
            composition.push_back(nums[i]);
            isUsed[nums[i]+100] = true; // 修改当前元素的使用状态
            backTrack(nums,i+1);
            composition.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backTrack(nums,0);
        return result;
    }
};

全排列

题干

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

链接：. - 力扣（LeetCode）

思路和代码

递归法

全排列中，每个排列的大小是固定的，我们递归进入下一个排列的位置，for 循环改变该排列位置上的元素。

递归参数和返回值：参数是传入的整数数组和本层递归的起始位置 stratIndex，无返回值。
递归终止条件：当排列的大小已经等于数组的大小时，将排列插入结果集，并返回。
递归顺序：在本层递归中固定好当前元素后，继续递归进行全排列，在下一层递归中将数组中所有其余的元素遍历一遍。因此我们需要用数组 isUsed 记录哪些元素已经被使用过。

class Solution {
public:
    bool isUsed[10]; // 该数组记录元素是否已经被使用过
    vector<int> path;
    vector<vector<int>> result;
    void findPath(vector<int> &nums,int startIndex){
        if (path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        // 每层都要从 0 开始搜索，因为排列是有序的，[1,2]和[2,1]属于两种不同的排列
        for (int i = 0; i < nums.size(); ++i) {
            if (isUsed[i]){ // 该元素已经在排列中被用过，跳过
                continue;
            }
            path.push_back(nums[i]);
            isUsed[i] = true; // 修改当前元素的使用状态
            findPath(nums,i+1);
            path.pop_back();
            isUsed[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        findPath(nums,0);
        return result;
    }
};

全排列Ⅱ

题干

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

链接：. - 力扣（LeetCode）

思路和代码

本题就是在上一题的思路上进行去重。去重的思路之前说过很多，也就是在当前 for 循环中如果有重复的元素，则跳过。

方法一：用集合 set 去重

class Solution {
public:
    bool isUsed[10];
    vector<int> path;
    vector<vector<int>> result;
    void backTrack(vector<int> &nums){
        if (path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        unordered_set<int> uSet; // 记录当前 for 循环遍历过的元素!!!
        for (int i = 0; i < nums.size(); ++i) {
            if (isUsed[i]) continue;
            if (uSet.find(nums[i]) != uSet.end()) continue; // 去重!!!
            path.push_back(nums[i]);
            isUsed[i] = true;
            uSet.insert(nums[i]);
            backTrack(nums);
            path.pop_back();
            isUsed[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        backTrack(nums);
        return result;
    }
};

方法二：先排序，再用数组去重

class Solution {
public:
    bool isUsed[10];
    vector<int> path;
    vector<vector<int>> result;
    void backTrack(vector<int> &nums){
        if (path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            if (isUsed[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !isUsed[i-1]){ // 对树层去重
                continue; // 去重！！
            }
            path.push_back(nums[i]);
            isUsed[i] = true;
            backTrack(nums);
            path.pop_back();
            isUsed[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        backTrack(nums);
        return result;
    }
};

查看全文

http://www.kler.cn/a/280385.html