侧边栏壁纸
博主头像
amazingK博主等级

大力出奇迹

  • 累计撰写 48 篇文章
  • 累计创建 12 个标签
  • 累计收到 33 条评论

目 录CONTENT

文章目录

【每日一题】子集

amazingK
2021-03-31 / 0 评论 / 3 点赞 / 860 阅读 / 990 字
温馨提示:
本文最后更新于 2021-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

示例 1:

输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]

回溯:

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;//前置条件
        Arrays.sort(nums);//排序,确保所有方案都具有单调性
        backtrack(0, nums, res, new ArrayList<>());//第一次搜索
        return res;

    }

    public void backtrack(int idx, int[] nums, List<List<Integer>> res, List<Integer> tmp_list) {
        res.add(new ArrayList<>(tmp_list));//每次搜索当前元素,先把当前元素的链表或传进来的链表加载成一条新链表压进res
        for (int i = idx; i < nums.length; i++) {
            if (i > idx && nums[i - 1] == nums[i]) continue;//当i > idx,意思如果进入某一子循环,且当前元素与上一元素相等,则直接continue
            tmp_list.add(nums[i]);//正常往当前链表加入元素
            backtrack(i + 1, nums, res, tmp_list);
            tmp_list.remove(tmp_list.size() - 1);//节省空间!
        }
    }
}
3
  1. qrcode alipay
  2. qrcode weixin
  • 3
    1. qrcode alipay
    2. qrcode weixin
博主关闭了当前页面的评论
">