Simple Recursive Solution


  • 0
    public static List<List<Integer>> permute(int[] num) {
    	List<List<Integer>> perms = new ArrayList<List<Integer>>();
    	List<Integer> nums = new ArrayList<Integer>();
    	for(int i:num) nums.add(i);
    	perms = permute(nums,new ArrayList<Integer>());
    	return perms;
    }
    public static List<List<Integer>> permute(List<Integer> start, List<Integer> end) {
    	List<List<Integer>> perms = new ArrayList<List<Integer>>();
    	if(start.size()<=1) {
    		List<Integer> newperm = new ArrayList<Integer>(start);
    		newperm.addAll(end);
    		perms.add(newperm);
    	}
    	else {
    		for(int i=0;i<start.size();i++) {
    			List<Integer> newstart = new ArrayList<Integer>();
    			newstart.addAll(start.subList(0, i));
    			newstart.addAll(start.subList(i+1,start.size()));
    			List<Integer> newend = new ArrayList<Integer>(end);
    			newend.add(start.get(i));
    			perms.addAll(permute(newstart,newend));
    		}
    	}
    	return perms;
    }
    

    Example:
    for the array [1,2,3] the List of permutations is given by the permutations of the array of n-1 length combined with the extracted element from the original array in each possible position of the permutations in the array of length n-1:

    permute(1,2,3) = 1 X permute(2,3) = 
    1 X ((2,3)(3,2)) = ((1),2,3),(2,(1),3),(2,3,(1)),((1),3,2),(3,(1),2),(3,2,(1))

Log in to reply
 

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