leetcode 90 子集2 js

比眉伴天荒 2022-11-12 08:16 154阅读 0赞

# leetcode 90 子集2 #

给定一个可能包含重复元素的整数数组 ***nums***，返回该数组所有可能的子集（幂集）。

\*\*说明：\*\*解集不能包含重复的子集。

**解题思路：**

对于数组中的每一个数字，有两种状态，取或不取。这个问题为一个树形问题，故采用回溯法解决。难点在于如何去重，即剪枝。

*  将数组从小到大排序，重复数字，只取第一个。
 *  一个数字有两种状态：
    
    1、不取，直接存入结果数组
    
    2、取，继续往后搜索。

**刻意联系的思路：**

1、递归树，状态变量：当前下标和新数组

![image-20210314153106066][]

2、递归出口：当前下标到达末尾，即搜索完毕。

3、选择列表：从当前下标数字往后的数字选取，存入新数组中

**若存在重复数字，只取第一次出现的数字，接着continue**

4、剪枝，去重

5、撤销操作：新数组中pop

var subsetsWithDup = function (nums) { 
      let len = nums.length
      nums.sort((a, b) => a - b);
      const res = [];
      helper();
      return res;
    
      function helper(temp = [], start = 0) { 
        //不选择当前数字，直接push
        res.push(temp);
        //当全选时，退出
        if (temp.length === len) return;
        //选择列表
        for (let i = start; i < len; i++) { 
          //相同元素只取第一个
          if (i > start && nums[i] === nums[i - 1]) continue
          temp.push(nums[i]);
          helper(temp.slice(), i + 1);
          temp.pop();
        }
      }
    
    };
    
    
    console.log(subsetsWithDup([1, 2, 2]));

[image-20210314153106066]: /images/20221022/33b45c989dd447328a74ba4df00039ae.png

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关 90. 子集 II

90. 子集 II 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按任

偏执的太偏执、/ 2024年03月30日 12:09/ 0 赞/ 75 阅读

相关 LeetCode-90. 子集 II

题目来源 [90. 子集 II][90. _ II] 题目思路建议先把这两道题做了，在做这道 [40.组合总和II][40._II] [78. 子集][7

素颜马尾好姑娘i/ 2024年03月26日 14:24/ 0 赞/ 56 阅读

相关 90.子集II

90.子集II 题干描述解题思路补充总结题干描述 [力扣入口][Link 1] 给定一个可能包含重复元素的整数数组 nums，返

深藏阁楼爱情的钟/ 2023年10月16日 13:54/ 0 赞/ 39 阅读

相关 LeetCode 90子集Ⅱ&91解码方法

> 微信搜一搜：`bigsai` 专注于Java、数据结构与算法，一起进大厂不迷路！ > 算法文章题解全部收录在github仓库[bigsai-algorithm][],求

叁歲伎倆/ 2022年12月30日 14:50/ 0 赞/ 155 阅读

相关【递归】 LeetCode90. 子集 II

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

以你之姓@/ 2022年12月03日 05:21/ 0 赞/ 162 阅读

相关 LeetCode90. 子集 II

难度：`中等` 题目描述：给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。返回的解集中，子集

阳光穿透心脏的1/2处/ 2022年11月15日 12:23/ 0 赞/ 127 阅读

相关 leetcode 90 子集2 js

leetcode 90 子集2 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 \\说明：\\解集不能包含重复的子集。解题思路：

比眉伴天荒/ 2022年11月12日 08:16/ 0 赞/ 155 阅读

相关 LeetCode 90.Subsets II (子集 II)

题目描述：给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例: 输入: [1,2,2]

梦里梦外;/ 2022年05月10日 10:24/ 0 赞/ 163 阅读

相关 leetcode-90-子集②

题目描述： ![1509441-20190711173348435-992965423.png][] 方法一：回溯 class Solution:

妖狐艹你老母/ 2021年11月29日 23:46/ 0 赞/ 265 阅读

相关 leetcode：90. 子集 II（java dfs）

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例: 输入: [1,2,2] 输出:

深藏阁楼爱情的钟/ 2021年09月28日 09:04/ 0 赞/ 286 阅读