Java solution, recursive, no global variants


  • 2
    L

    The basic idea is to insert an integer element to each position of a permuted sequence at different positions. The idea is borrowed from Career Cup.

    public List<List<Integer>> permute(int[] num) {
    	if (num == null) return null;
    	if (num.length == 0) return new ArrayList<List<Integer>>();
    	return permutehelper(num, 0);
    }
    
    public List<List<Integer>> permutehelper(int[] num, int start){
    	List<List<Integer>> output = new ArrayList<List<Integer>>();
    
    	if (start == num.length - 1){
    		List<Integer> single = new ArrayList<Integer>();
    		single.add(num[start]);
    		output.add(single);
    		return output;
    	}
    	List<List<Integer>> subpermute = permutehelper(num,start+1);
    	for (List<Integer> seq : subpermute){
    		for (int i=0;i<=seq.size();++i){
    			List<Integer> newseq = new ArrayList<Integer>(seq);
    			newseq.add(i, num[start]);
    			output.add(newseq);
    		}
    	}
    	return output;
    }

Log in to reply
 

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