代码随想录第28天|回溯算法

491. 非递减子序列

思路:

• 不可以排序, 否则会改变元素的顺序
• 对收获的结果有要求, num.size() >= 2, 且 num[i - 1] < num[i]
• 需要进行去重, 不能使用排序后的方法去重
• 每一层可用 unordered_set 去重
• 组合问题, for 遍历需要标记起始位置

bug:

• 一定要先判断元素是否重复, 再将元素插入
  

//正确步骤
if (used.find(nums[i]) != used.end()) {
    continue;
} else if (res_tem.empty()) { // 重复元素
    res_tem.push_back(nums[i]);
} else if (res_tem.back() > nums[i]) { // 非递增
    continue;
} else {
    res_tem.push_back(nums[i]);
}

//错误步骤
//当res_tem为空时, 会将重复元素也添加, 一定需要先判断元素是否有使用
if (res_tem.size() == 0) { 
    res_tem.push_back(nums[i]);
} else if (used.find(nums[i]) != used.end()) { //重复元素
    continue;
} else if (!(res_tem.back() <= nums[i])) {  //非递增
    continue;
} else {
    res_tem.push_back(nums[i]);
}

class Solution {
public:
    vector<vector<int>> res;
    vector<int> res_tem;
    void myoperator(vector<int>& nums, int index) {
        if (res_tem.size() >= 2) {
            res.push_back(res_tem);
        }
        unordered_set<int> used;
        for (int i = index; i < nums.size(); i++) {
            
            if (used.find(nums[i]) != used.end()) {
                continue;
            } else if (res_tem.empty()) { // 重复元素
                res_tem.push_back(nums[i]);
            } else if (res_tem.back() > nums[i]) { // 非递增
                continue;
            } else {
                res_tem.push_back(nums[i]);
            }
			// 等效操作
            // if (!res_tem.empty() && nums[i] < res_tem.back()) {
            //     continue;
            // }
            // if (used.find(nums[i]) != used.end()) {
            //     continue;
            // }
            // res_tem.push_back(nums[i]);

            used.insert(nums[i]);
            myoperator(nums, i + 1);
            res_tem.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        myoperator(nums, 0);
        return res;
    }
};

46.全排列

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

思路:

• 不能使用index来跳过元素, 因为与顺序有关, 所以遍历从 i = 0 开始
• 每个元素都要遍历, 可以使用 used 数组去重
• 无法用 unordered_set 去重, 每层树枝都有相互关联, 不是去除重复数字操作

class Solution {
public:
    vector<vector<int>> res;
    vector<int> res_tem;
    vector<bool> uesed;
    void myoperator(vector<int>& nums) {
        if (res_tem.size() == nums.size()) {
            res.push_back(res_tem);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (uesed[i] == true) {
                continue;
            }
            uesed[i] = true;
            res_tem.push_back(nums[i]);
            myoperator(nums);
            uesed[i] = false;
            res_tem.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        uesed = vector<bool>(nums.size(), 0);
        myoperator(nums);
        return res;
    }
};

47. 全排列 II

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


思路:

• 取叶子节点, 中间需要去除, 相同数层之间不能用同样的数值
• 排列则需要从0开始, 使用used标记使用过的元素

class Solution {
public:
    vector<vector<int>> res;
    vector<int> res_tem;
    vector<bool> flag;
    void myoperator(vector<int>& nums) {
        if (res_tem.size() == nums.size()) {
            res.push_back(res_tem);
            return;
        }
        unordered_set<int> used;
        for (int i = 0; i < nums.size(); i++) {
            if (used.find(nums[i]) != used.end()) {
                continue;
            }
            if (flag[i] == true) {
                continue;
            }
            flag[i] = true;
            used.insert(nums[i]);
            res_tem.push_back(nums[i]);
            myoperator(nums);
            flag[i] = false;
            res_tem.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        flag = vector<bool>(nums.size(), false);
        myoperator(nums);
        return res;
    }
};

51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

参考

37. 解数独



参考