LeetCode_回溯_中等_90.子集II

x33g5p2x  于2022-04-20 转载在 其他  
字(1.0k)|赞(0)|评价(0)|浏览(365)

1.题目

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集不能包含重复的子集。返回的解集中,子集可以按任意顺序排列。

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

示例 2:
输入:nums = [0]
输出:[[],[0]]

提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/subsets-ii

2.思路

(1)回溯
在做本题之前,可以先了解LeetCode_回溯_中等_78.子集,这两题十分类似,只不过本题中的元素可能重复,而78.子集这题中的元素不重复。那么现在的关键在于如何去掉/避免重复的子集。我们可以考虑现将数组 nums 进行排序,这样可以将相等的元素排在一起。然后在回溯过程中的每次做选择前,先对要作用的元素进行判断,如果当前元素与前一个作用的元素相等,则说明当前元素是一个重复元素,因此跳过对该元素的操作。

3.代码实现(Java)

  1. //思路1————回溯
  2. class Solution {
  3. //res用于保存最终的结果
  4. List<List<Integer>> res = new LinkedList<>();
  5. //track用于记录回溯的路径
  6. LinkedList<Integer> track = new LinkedList<>();
  7. public List<List<Integer>> subsetsWithDup(int[] nums) {
  8. //对数组 nums 进行升序排序
  9. Arrays.sort(nums);
  10. backtrack(nums, 0);
  11. return res;
  12. }
  13. public void backtrack(int[] nums, int start) {
  14. res.add(new LinkedList(track));
  15. //回溯算法框架
  16. for (int i = start; i < nums.length; i++) {
  17. //去除重复元素对生成的子集的影响
  18. if (i > start && nums[i] == nums[i - 1]) {
  19. continue;
  20. }
  21. //做选择
  22. track.add(nums[i]);
  23. backtrack(nums, i + 1);
  24. //撤销选择
  25. track.removeLast();
  26. }
  27. }
  28. }

相关文章