子集2

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

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

利用回溯去重

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);//排序为了去重
        List<Integer> list = new ArrayList<>();

        for (int i = 2; i < nums.length; i++) {
            backtrack(nums, list, 0, i);
        }
        for (int i = 0; i < nums.length; i++) {//添加单个元素
            if (!result.contains(Arrays.asList(nums[i]))) {
                result.add(Arrays.asList(nums[i]));
            }
        }
        
        List<Integer> list1 = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {//添加所有元素
            list1.add(nums[i]);
        }

        if(!result.contains(list1)){
            result.add(list1);
        }

        result.add(Arrays.asList());//添加空元素
        return result;
    }
    
    /**
     * 从数组nums中选取n个数字
     * @param nums 带选取的数组
     * @param tmpList 当前选取的数字集合
     * @param start 当前遍历的开始位置
     * @param n 要选取的数字的数量
     */
    public void backtrack(int[] nums, List<Integer> tmpList, int start, int n) {
        if (tmpList.size() == n) {
            if (!result.contains(tmpList)) {
                result.add(new ArrayList<>(tmpList));
            }
            return;
        }
        for (int i = start; i < nums.length; i++) {
            tmpList.add(nums[i]);
            backtrack(nums, tmpList, i + 1, n);
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

回溯的精简写法

class Solution {
    List<List<Integer>> ans;
    List<Integer> tmp;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ans = new ArrayList<>();
        tmp = new ArrayList<>();
        int l = nums.length;
        if (l == 0) return ans;
        Arrays.sort(nums);
        dfs(0, nums);
        return ans;
    }
    private void dfs(int i, int[] nums) {
        ans.add(new ArrayList<>(tmp));
        for (int j = i; j < nums.length; j++) {
            if (j > i && nums[j] == nums[j-1]) continue;
            tmp.add(nums[j]);
            dfs(j+1, nums);
            tmp.remove(tmp.size()-1);
        }
    }
}

参考文献

IRVLIN的题解

赏

谢谢你请我吃糖果

微信