Both BFS and DFS solution in Java with explanation.


  • 0
    Y
    public class Solution {    
        /**
         * iteration
         * The key idea here is that we can only add a number to the end of the all of the subsets in the result if and only if current number if not a duplicate of its previous one. 
         * Otherwise, we can only add current number to the subsets that is generated from the previous step. 
         * For example, for [1,2,2]
         * The initial result is [[]].
         * In the first iteration, we add nums[0] into every subset in the result and the result becomes [[], [1]].
         * In the second iteration, nums[1] != nums[0], so we add nums[1] to every subset in the result and the result becomes[[], [1], [2], [1,2]]
         * In the third iteration, nums[2] == nums[1], we can only add it to the subsets newly generated by the previous step, whose index in the result is 2 to the end, which is still kept by the size vairable in our function and will be modified later to be current size of the result in order to iterate the result. So we assign this value to start.
         * Then we add nums[2] to every subset from result[2] to result[result.size() - 1] and we get: [[], [1], [2], [1,2], [2,2], [1,2,2]]
         * At this time, the loop ends and we can return result list. 
        **/
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            result.add(new ArrayList<>());
            if (nums == null || nums.length == 0) {
                return result;
            }
            
            Arrays.sort(nums);
            int size = 0;
            int start = 0;
            for (int i = 0; i < nums.length; i++) {
                start = i >= 1 && nums[i] == nums[i - 1] ? size : 0;
                
                size = result.size();
                for (int j = start; j < size; j++) {
                    List<Integer> tmp = new ArrayList<>(result.get(j));
                    tmp.add(nums[i]);
                    if (!result.contains(tmp)) {
                        result.add(tmp);
                    }
                }
            }
            return result;
        }
        
        
        
        
        
        /**
         * Backtracking
        **/
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            result.add(new ArrayList<>());
            
            if (nums == null || nums.length == 0) {
                return result;
            }
            
            Arrays.sort(nums);
            backTrack(nums, 0, result, new ArrayList<Integer>());
            return result;
        }
        
        private void backTrack(int[] nums, int start, List<List<Integer>> ret, List<Integer> curr) {
            int i = start;
            while (i < nums.length) {
                //skip all duplicates except current number is the start of this iteration
                //In other words, we avoid duplicates by letting every different number be the start of the subresults only once.
                while (i > start && i < nums.length && nums[i] == nums[i - 1] ) { 
                    i++;
                }
                if (i < nums.length) {
                    curr.add(nums[i]);
                    ret.add(new ArrayList<>(curr));
                    backTrack(nums, i + 1, ret, curr);
                    curr.remove(curr.size() - 1);
                    i++;
                }
            }
        }
    }
    

  • 0
    A

    @YaokaiYang result.contains() is linear scan, just like any other solutions that rely on search for duplicates, your time complexity will always be N times higher than others that don't employ checking on duplicates.


Log in to reply
 

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