Intuitive recursive soln (similar to DP) in Java ~9ms


  • 0
    S

    Find all permutations till i-1. Add ith item at all possible places.

    class Solution {
        public List<List<Integer>> permute(int[] nums) {
            if(nums.length ==0) return new ArrayList<>();
            return permuteUtil(nums, nums.length-1);
        }
        
        private List<List<Integer>> permuteUtil(int[] nums, int i){
            
            List<List<Integer>> permuteTillIPlusOne = new ArrayList<>();
            
            if(i==0){
                List<Integer> temp = new LinkedList<>();
                temp.add(nums[i]);
                permuteTillIPlusOne.add(temp);
                return permuteTillIPlusOne;
            }
            
            List<List<Integer>> permuteTillI = permuteUtil(nums, i-1);      
            
            for(List<Integer> list : permuteTillI){            
                for(int j=0; j<=list.size(); j++){
                    List<Integer> temp = new LinkedList<>(list);
                    temp.add(j, nums[i]);
                    permuteTillIPlusOne.add(temp);
                }
            }
            
            return permuteTillIPlusOne;
        }
    }
    

Log in to reply
 

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