Simple python solution without extra space.


  • 63
    Q
    class Solution:
        # @param num, a list of integer
        # @return a list of lists of integer
        def subsetsWithDup(self, S):
            res = [[]]
            S.sort()
            for i in range(len(S)):
                if i == 0 or S[i] != S[i - 1]:
                    l = len(res)
                for j in range(len(res) - l, len(res)):
                    res.append(res[j] + [S[i]])
            return res
    

    if S[i] is same to S[i - 1], then it needn't to be added to all of the subset, just add it to the last l subsets which are created by adding S[i - 1]


  • 1
    P

    Excellent solution! "l" was the number of subsets created by the last s[j] where s[j] != s[j-1].


  • 0

    Nice thoughts...
    I met with something strange while implementing similar idea regarding to TLE

    Solution:
    # @param num, a list of integer
    # @return a list of lists of integer
    def subsetsWithDup(self, S):
        res = [[]]
        S.sort()
        for i in range(len(S)):
            if i == 0 or S[i] != S[i - 1]:
                l = len(res)
            for j in range(len(res) - l, len(res)):
                res.append(res[j] + [S[i]]) # MAKE A CHANGE HERE : res[j].append(S[i]);res.append(res[j])
        return res
    

    append should work twice fast compared to '+' operation. But I got TLE after using append.
    Any explanation?


  • 0
    Q

    becasue you have changed res[j] which shouldn't be changed.


  • 0
    O

    damnnn nice one, the way you use l is really clever and fit into the loop to record the correct amount of subsets we need to process!


  • 0
    W

    @qqz003

    Your setting about the range of 'j' is awesome!

    One can find out its delicacy with few test cases.


  • 0
    A

    Really clever! Especially on length manipulation of results list

    Here's the java version

        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> results = new ArrayList<>();
            results.add(new ArrayList<>());     // the [] set
    
            Arrays.sort(nums);
    
            int updateToLength = 0;
    
            for (int i = 0; i < nums.length; i++) {
                // new num, update all prev subsets
                if (i == 0 || nums[i] != nums[i-1]) {
                    updateToLength = results.size();
                }
    
                List<List<Integer>> newSubsets = new ArrayList<>();
                // if new num, append to all prev
                // if dup, only append to subsets created by this dup num
                // so increase in digits 14 => 144, 1444
                for (int s = results.size() - updateToLength; s < results.size(); s++) {
                    List<Integer> subset = results.get(s);
                    List<Integer> appendSubset = new ArrayList<>(subset);
                    appendSubset.add(nums[i]);
                    newSubsets.add(appendSubset);
                }
                results.addAll(newSubsets);
            }
            return results;
        }
    

  • 0
    T

    Is the time complexity O(2^N)?


  • 0
    G

    How smart you are!!!


  • 0
    L

    Brilliant treatment on using the right items of old result to generate new items! This is really a clever example to show the ideas of backtracking! Thank you!


Log in to reply
 

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