回溯
解题思路
解题思路与 leetcode🧑💻 78. 子集 有些相似，不同之处是去重的方式不太一样；
leetcode🧑💻 78. 子集 去重之前需要先排序，再对相邻的元素进行去重，此题不一样；
此题要求求出 非递减子序列 ，故不能进行排序，而且要对 横向搜素 时去重，则可以对横向搜索的时候定义一个 hash 结构的 set 集合 ，将每个元素放入其中，如果遇到重复的元素，则直接跳过即可；
图解
实现代码
var findSubsequences = function (nums) {
const res = [];
backtrack(res, nums, 0, []);
return res;
};
const backtrack = (res, nums, startInx, path) => {
if (path.length >= 2) res.push([...path]);
const set = new Set();
for (let i = startInx; i < nums.length; i++) {
// 剪枝：下一个要入栈的元素，必须 >= 栈顶元素
if (path.length > 0 && path[path.length - 1] > nums[i]) continue;
// 剪枝：去掉重复项
if (set.has(nums[i] + 100)) continue;
// 此行注释掉的是：子集去重的方式
// if (i > startInx && nums[i - 1] >= nums[i]) continue;
set.add(nums[i] + 100);
path.push(nums[i]);
backtrack(res, nums, i + 1, path);
path.pop();
}
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 90. 子集 II
上一篇
评论
