Standard DFS Java Solution


  • 24
    Z
    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> result= new ArrayList<>();
            dfs(nums,0,new ArrayList<Integer>(),result);
            return result;
        }
        
        public void dfs(int[] nums,int index,List<Integer> path,List<List<Integer>> result){
            result.add(path);
            for(int i=index;i<nums.length;i++){
                if(i>index&&nums[i]==nums[i-1]) continue;
                List<Integer> nPath= new ArrayList<>(path);
                nPath.add(nums[i]);
                dfs(nums,i+1,nPath,result);
            }
        }
    }

  • 0
    Y

    Great hint!!


  • 2
    S

    Alternative solution modified from: https://leetcode.com/discuss/29631/java-subsets-solution/29631/java-subsets-solution

    Only added one line: if(i>index&&nums[i]==nums[i-1]) continue;

    public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
       List<List<Integer>> result = new ArrayList<List<Integer>>();
    
        if(nums.length == 0){
            return result;
        }
    
        Arrays.sort(nums);
        dfs(nums, 0, new ArrayList<Integer>(), result);
        return result; 
    }
    
    public void dfs(int[] nums, int index, List<Integer> path, List<List<Integer>> result){
        result.add(new ArrayList<Integer>(path));
    
        for(int i = index; i < nums.length; i++){
            if(i>index&&nums[i]==nums[i-1]) continue;
            path.add(nums[i]);
            dfs(nums, i+1, path, result);
            path.remove(path.size()-1);
        }
    }
    

    }


  • 0
    K

    @zn13621236 Much better than my recursive solution:

    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            if (nums == null || nums.length == 0) {
                return Collections.<List<Integer>>emptyList();
            }
            
            Arrays.sort(nums);
            Set<Integer> set = new HashSet<>();
            List<List<Integer>> result = new ArrayList<>();
            recurse(nums, 0, set, result);
            return result;
        }
        
        private int recurse(int[] nums,
                            int index,
                            Set<Integer> set,
                            List<List<Integer>> result) {
            // base case
            if (index == nums.length) {
                result.add(new LinkedList<Integer>());
                return 1;
            }
            
            // recursive case
            int delta = recurse(nums, index + 1, set, result);
            int finalSize = result.size();
            
            if (set.contains(nums[index])) {
                for (int i = finalSize - delta; i < finalSize; i ++) {
                    LinkedList<Integer> newList = new LinkedList<>(result.get(i));
                    newList.addFirst(nums[index]);
                    result.add(newList);
                }
                return delta;
            }
            
            set.add(nums[index]);
            for (int i = 0; i < finalSize; i ++) {
                LinkedList<Integer> newList = new LinkedList<>(result.get(i));
                newList.addFirst(nums[index]);
                result.add(newList);
            }
            return finalSize;
        }
    }
    

Log in to reply
 

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