Accepted Java Solution. Simple & Clear


  • 0
    V

    Time complexity 2 ^ n, inside the second for loop, need check whether has duplicated elements, if has, skip, if not add the element

    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] num) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            result.add(new ArrayList());
            
            Arrays.sort(num);
            
            for(int i : num){
                List<List<Integer>> temp = new ArrayList<List<Integer>>();
                for(List<Integer> sub : result){
                    List<Integer> inner = new ArrayList<Integer>(sub);
                    inner.add(i);
                    if(!result.contains(inner))
                        temp.add(inner);
                }
                result.addAll(temp);
            }
            return result;
        }
    }

  • 0
    V

    Algorithm is interesting, sometimes...


  • 0
    A

    Hi, I noticed you called ArrayList.contains method in the secondary loop, which takes O(n) time. So is seems that the complexity of your answer is O(n^3) ?


  • 0
    V

    The overall time complexity is 2^n, which is larger than n^3, so is 2^n


  • 0
    A

    I see. Sorry I mistakenly thought you mean n^2...


Log in to reply
 

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