My Java Recursive Solution


  • 0
    T
    public List<List<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        return subset(num, 0, new ArrayList<List<Integer>>());
        
    }
    
    public List<List<Integer>> subset(int[] num, int index, List<List<Integer>> newNext) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        if (index >= num.length) {
            List<Integer> list = new ArrayList<Integer>();
            result.add(list);
            return result;
        }
    
        List<List<Integer>> nextList = subset(num, index + 1, newNext);
        List<List<Integer>> iterate = null;
    
        iterate = (index + 1 < num.length && num[index] == num[index+1]) ? newNext : nextList;
    	for (List<Integer> l : iterate) {
    		List<Integer> newList = new ArrayList<Integer>(l);
            newList.add(0, num[index]);
            result.add(newList);
    	}
       
        newNext.clear();
        for (List<Integer> l : result) {
        	newNext.add(l);
        }
        
        result.addAll(nextList);
        return result;
    }
    

    I tried to solve this problem using recursion. The key idea is keeping "newNext" array that contains newly added list. Any improvement?


  • 0
    R

    Use a HashSet as member variable of Solution class. Check if the recent sub list is already present in the result list.


Log in to reply
 

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