Subsets vs. Subsets II: Add only 3 more lines to Subsets solution


  • 5

    The solution of subset II could be easily derived from the answer of subset I.

    Here is my answer of subset I:

    public class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> res = new ArrayList<>(); 
            res.add(new ArrayList<>()); 
            
            for (int num: nums) {
                List<List<Integer>> resDup = new ArrayList<>(res);
                for (List<Integer> list:resDup) {
                    List<Integer> tmpList = new ArrayList<>(list);
                    list.add(num);
                    res.add(tmpList); 
                }
            }
            return res; 
        }
    }
    

    In this problem, we need to change two things:

    1. Sort the input nums, so that we won't get lists such as [1,4] and [4, 1] at the same time.
    2. Check duplicates when adding new list to res.
      Here is Subset II solution based on subset I solution:
    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            res.add(new ArrayList<Integer>()); 
            Arrays.sort(nums); //important: sort nums 
            
            for (int num: nums) {
                List<List<Integer>> resDup = new ArrayList<>(res);
                for (List<Integer> list: resDup) {
                    List<Integer> tmp = new ArrayList<>(list);
                    tmp.add(num);
                    if (!res.contains(tmp))  //check duplicates
                        res.add(tmp);
                }
            }
            return res; 
        }
    }
    

  • 0
    R

    I cannot believe this answer isn't the most up voted one.


  • 3
    A

    @randing89 Apparently whoever upvoted didn't care about time complexity at all.
    contains() is basically linear search, so for every loop, you search the whole list ....


  • 0

    This solution will not work as every list is a new list so when it will try to do contains in the set the set will not be able to find the list as it will not be searching on the elements in the list but just the object id


  • 0
    J

    Nice solution @summer_jinyu. An optimization would be to use a memo (hash table) instead of using .contains as they runs in linear time.

    A simple hash table at the top, then create a memoKey with the tmp array and check it against that.


  • 0
    O

    @viditbhatia-hotmail-com contains() method internally will call equals() method,
    Below is what equals() method will do:

    Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. (Two elements e1 and e2 are equal if (e1==null ? e2==null : e1.equals(e2)).) In other words, two lists are defined to be equal if they contain the same elements in the same order. This definition ensures that the equals method works properly across different implementations of the List interface.


Log in to reply
 

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