【回溯算法】leetcode90.子集II題目描述（傳送門）思考算法思路解題思路&代碼解析

題目描述（傳送門）

給定一個可能包含重複元素的整數數組 nums，傳回該數組所有可能的子集（幂集）。

說明：解集不能包含重複的子集。

示例:

輸入: [1,2,2]
輸出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
           

思考

這道題與之前子集不同的是有了重複元素。

算法思路

解題思路&代碼解析

【回溯算法】leetcode78.子集

我們隻需要對昨天代碼做兩部改進：

1. 對原始數組進行排序
2. 對子集借助Set去重

【小象算法Java版】第一節：連結清單（上）

這裡邊我們求解相交連結清單也是用到Set可以參考。

package com.wenhui.lession4;

import java.util.*;

/**
 * @ClassName leetcode90
 * @Description ：TODO
 * @Author Josvin
 * @Date 2021/02/07/22:36
 */
public class leetcode90 {
    public static List<List<Integer>> subsets(int[] nums) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> listList = new ArrayList<>();
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<>();
        set.add(list);
        listList.add(list);
        subsetsHelper(0, nums, list, listList,set);
        return listList;
    }

    private static void subsetsHelper(int i, int[] nums, List<Integer> list, List<List<Integer>> listList, Set<List<Integer>> set) {
        if (i >= nums.length) {
            return;
        }
        list.add(nums[i]);
        if (!set.contains(new ArrayList<>(list))) {
            listList.add(new ArrayList<>());
            set.add(new ArrayList<>(list));//
        }
        subsetsHelper(i + 1, nums, list,listList, set);
        list.remove(list.size() - 1);
        subsetsHelper(i + 1, nums, list, listList,set);
    }
}