My solution using bit masks


  • 6
    M

    Here is my solution using bit masks.

    public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] num) {
        //Sort the input
        Arrays.sort(num);
        int numberSets = 1 << num.length;
        List<List<Integer>> solution = new LinkedList<>();
        for(int i = 0; i<numberSets; i++){
            List<Integer> subset = new LinkedList<Integer>();
            for(int j = 0; j< num.length; j++){
                if((i & (1 << j)) > 0){
                    subset.add(num[j]);
                }
            }
            if(!solution.contains(subset))
                solution.add(subset);
        }
        
        return solution;
    }
    

    }


  • 16
    S
    if(!solution.contains(subset))
        solution.add(subset);
    

    This is too slow.


  • 0
    S
    class Solution {
    public:
        vector<vector<int> > subsetsWithDup(vector<int> &S) {
            int n = S.size();
            vector <vector <int> > res;
            for (int i = 0; i < (1 << n); i++) {
                vector <int> cur;
                for (int j = 0; j < n; j++) {
                    if ((i >> j) & 1) {
                        cur.push_back(S[j]);
                    }
                }
                sort(cur.begin(), cur.end());
                res.push_back(cur);
            }
            sort(res.begin(), res.end());
            res.resize(unique(res.begin(), res.end()) - res.begin());
            sort(res.rbegin(), res.rend());
            return res;
        }
    };
    

    Same idea but with sorting and eliminating duplicates.

    O(2^n * n) instead of O(2^n * n * 2^n)


  • 1
    F

    You can use Set<List<Integer>> instead of List<List<Integer>> to speed up checking for duplicate subsets.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.