Day25- 回溯算法part05

一、非递减子序列

题目一：491. 非递减子序列

491. 非递减子序列

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

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

• 使用set<vector<int>>来存储所有唯一的递增子序列。
• dfs函数是用于递归地构建子序列的。它接受当前索引start和当前构建的序列path。
• 如果path的长度大于1，则将其添加到结果集中。
• 遍历nums数组，只有当当前元素大于等于path中的最后一个元素时，才将其添加到path中，并递归地继续搜索。
• 每次递归返回后，回溯并移除path中的最后一个元素。

/*
 * @lc app=leetcode.cn id=491 lang=cpp
 *
 * [491] 非递减子序列
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        set<vector<int>> result_set; 
        vector<int> path;
        dfs(nums, 0, path, result_set);
        return vector<vector<int>>(result_set.begin(), result_set.end());
    }

private:
    void dfs(const vector<int>& nums, int start, vector<int>& path, set<vector<int>>& result_set) {
        if (path.size() > 1) {
            result_set.insert(path);
        }

        for (int i = start; i < nums.size(); i++) {
            if (path.empty() || nums[i] >= path.back()) {
                path.push_back(nums[i]);
                dfs(nums, i + 1, path, result_set);
                path.pop_back();
            }
        }
    }
};
// @lc code=end

二、全排列

题目一：46. 全排列?

46. 全排列

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

• backtrack函数是用于递归地构建排列的。它接受当前处理的索引start和当前构建的排列nums。
• 如果start等于nums的长度，意味着构建了一个完整的排列，将其添加到结果中。
• 对于start到nums.size()的每一个索引i，交换start和i位置上的元素，递归地调用backtrack，然后撤销交换（即回溯），以便于在下一次循环中尝试不同的元素。

/*
 * @lc app=leetcode.cn id=46 lang=cpp
 *
 * [46] 全排列
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        backtrack(nums, 0, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {
        if (start == nums.size()) {
            result.push_back(nums);
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            swap(nums[start], nums[i]);
            backtrack(nums, start + 1, result);
            swap(nums[start], nums[i]); 
        }
    }
};
// @lc code=end

题目二：47. 全排列II

47. 全排列 II

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

• 在每次递归中，遍历整个数组，而不是从start索引开始。
• 使用一个布尔数组used来标记已经被选择的元素。
• 如果当前元素与前一个元素相同，并且前一个元素没有被使用（表示已经处理了这种情况），则跳过当前元素。

/*
 * @lc app=leetcode.cn id=47 lang=cpp
 *
 * [47] 全排列 II
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end()); 
        vector<int> path;
        vector<bool> used(nums.size(), false);
        backtrack(nums, 0, path, used, result);
        return result;
    }

private:
    void backtrack(const vector<int>& nums, int index, vector<int>& path, vector<bool>& used, vector<vector<int>>& result) {
        if (index == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue; 
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // 跳过当前元素与前一个元素相同的情况

            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, index + 1, path, used, result);
            used[i] = false;
            path.pop_back();
        }
    }
};
// @lc code=end