Whether to take a duplicate subset with duplicate elements [how to take a subset? How to remove duplicates?]

Preface

Finding the key problem is a person's core ability , For example, take the non repeating subset with repeating elements , Two key issues are , First of all , How to get subsets ？ second , How to go heavy ？
For how to get subsets , This paper sorts out three ways ;
For how to remove weight , This paper sorts out two ways .

One 、 A subset of II

Two 、 Take a subset + duplicate removal

package everyday.bitManipulation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SubsetsWithDup {
    
    /* target: Non repeating subset .  How to get subsets ？ Constantly add an element .  How to go heavy ？ Sort +pre+ Record the location of the last group added . */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
    
        Arrays.sort(nums);
        
        List<List<Integer>> subsets = new ArrayList<>();
        subsets.add(new ArrayList<>());
        
        int pre = 1 << 31, begin = 0;
        for (int num : nums) {
    
            int i = 0, size = subsets.size();
            
            if (pre == num) i = begin;

            while (i < size) {
    
                List<Integer> el = new ArrayList<>(subsets.get(i++));
                el.add(num);
                subsets.add(el);
            }
            begin = size;
            pre = num;
        }
        return subsets;
    }

    /*  Above, we have explored two core issues , And I finished the problem solution in my own way .  Take a look at how the official advanced practice , That is, if the official solves the following two problems , 1- How to get subsets ？ Binary enumeration  +  Take this bit as 1 Collection elements for , Time complexity O(2^n^ * n) 2- How to go heavy ？ Sort  +  The two are equal  +  The previous one is in the subset  */
    public List<List<Integer>> subsetsWithDup2(int[] nums) {
    
        int n = nums.length;

        Arrays.sort(nums);

        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> subset = new ArrayList<>();

        for (int mask = 0; mask < 1 << n; mask++) {
    
            //  Take the element by every bit of binary .
            boolean isValid = true;
            for (int i = 0; i < n; i++) {
    
                //  Determine whether the element is in the current subset .
                if ((mask & 1 << i) != 0) {
    
                    if (i > 0 && nums[i] == nums[i - 1] && (mask >> i - 1 & 1) == 0) {
    
                        //  Duplicate occurs 
                        isValid = false;
                        break;
                    }
                    //  No repetition 
                    subset.add(nums[i]);
                }
            }
            //  Repeat, don't repeat and half cut the subset , If you don't repeat, you have to .
            if (isValid) subsets.add(new ArrayList<>(subset));
            //  Clear subset 
            subset.clear();
        }
        return subsets;
    }

    /*  Above, we have explored two core issues , And I finished the problem solution in my own way .  Take a look at how the official advanced practice , That is, if the official solves the following two problems , 1- How to get subsets ？ choice  or  Do not select the current element . 2- How to go heavy ？ Sort + The previous and currently selected elements do not appear at the same time  ->  Go beyond this subset . */
    public List<List<Integer>> subsetsWithDup3(int[] nums) {
    
        int n = nums.length;

        Arrays.sort(nums);

        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> subset = new ArrayList<>();

        dfs(nums, 0, false, subset, subsets);

        return subsets;
    }

    //  choose  or  No election , Consider n Elements , So it is (1 + 1)^n^
    private void dfs(int[] nums, int cur, boolean isChoosePre, List<Integer> subset, List<List<Integer>> subsets) {
    
        if (cur == nums.length) {
    
            subsets.add(new ArrayList<>(subset));
            return;
        }
        //  choice  or  Do not select the current element .
        //  Do not select the current element , Shit no 
        dfs(nums, cur + 1, false, subset, subsets);
        //  Select the current element , When cur - 1 But I have no choice , And they are equal , There must be duplicate subsets , Skip over .
        if (cur > 0 && nums[cur] == nums[cur - 1] && !isChoosePre) return;
        //  The front one chose  or  The front and back are not equal , Add elements normally , Generating subsets .
        //  Standard backtracking 
        subset.add(nums[cur]);
        dfs(nums, cur + 1, true, subset, subsets);
        subset.remove(subset.size() - 1);
    }
}

summary

1） Exercise yourself to find core problems / Ability to ask key questions .
2） Three ways to generate subsets , Add elements circularly | Binary enumeration | dfs Select or deselect elements
3） Two ways of judging subset repetition , Sort + Whether the front and back are equal | Sort + Whether the front and back are equal + Whether the front is selected

reference

[1] LeetCode A subset of II