Divide and conquer


  • 3
    L

    The problem can be solved through the 'divide-and-conquer' approach. Given a list of elements, in order to get all possible combinations of elements, one can obtain the solution in three steps (naturally recursive):

    1). take the first of element out of the list.

    2). obtain the combinations for the rest of the elements.

    3). add the element taken before to each of combination of step 2, then we got new combinations, other than the existing ones.

    Voila. Plus instead of sorting each combination, we could just the entire input list for once, since the above steps preserve the order among elements.

    private List<List<Integer>> rec_subsets(int []S, int begin){
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	
    	if(S.length == 0 || begin >= S.length){
    		List<Integer> emptyList = new ArrayList<Integer>();
    		result.add(emptyList);
    		return result;
    	}
    	
    	List<List<Integer>> rest = rec_subsets(S, begin+1);
    	
    	// Add the result from the rest of the problem.
    	result.addAll(rest);
    	
    	for(List<Integer> elem : rest){
    		ArrayList<Integer> newComb = new ArrayList<Integer>();
    		newComb.addAll(elem);		
    		elem.add(0, S[begin]);
    		
    		result.add(newComb);
    	}
    	
    	return result;
    }
    
    public List<List<Integer>> subsets(int[] S) {
    	        Arrays.sort(S);
    	return this.rec_subsets(S, 0);
    }

Log in to reply
 

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