回溯算法:排列问题II,去重方法全归纳!

发布时间:2023-12-27 23:51:52

回溯算法:排列问题II

在这里插入图片描述
思路,这道题也是需要去重,但和之前的去重又有些不同,对去重进行一下整理:

一般来说:组合问题和排列问题是在树形结构的叶子节点上收集结果,而子集问题就是取树上所有节点的结果

1.组合数问题:i > startIndex && nums[i] == nums[i - 1] 这是对同一树层的相邻且相同的元素进行去重,比如【1,2 ,3, 3,3,4】,对于一树枝上的相同元素无需去重
2. 递增子序列:利比上面稍微复杂,相同元素并没有相邻了,因此借用set进行去重,uset.find(nums[i]) != uset.end(),这是对同一层相同的元素进行去重,比如【1,2,3,1,1,1】,注意:set定义的是局部变量,用来控制每一层的循环
3. 排列问题I:借用全局的vector去重,这次的去重是对同一树枝进行去重,即上一层使用过的节点这一层不能使用,比如【1,2,3】,那么【1】的下一层子树就只能有【2,3】
4. 排列问题II:比排列问题稍微复杂,加入了相同元素,如果只考虑同一树枝去重的话势必会出现相同的排列方法,比如【1,1,2】以第一个【1】为首的排列,和以第二个【1】为首的排列就会出现重复元素。因此还要控制同一树层元素去重并且去重的是要未被使用过的数字!,举个例子:第一层:【1】,第二层:【1(树枝去重),1,2】,不能把第二层第二个【1】去重删去了
5. 详细见代码:

class Solution 
文章来源:https://blog.csdn.net/cckluv/article/details/114303272
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。