Java Clean Code - Two recursive solutions


  • 42
    C

    Bottom up? approach - 280ms

    public class Solution {
       public List<List<Integer>> permute(int[] nums) {
    		List<List<Integer>> permutations = new ArrayList<>();
    		if (nums.length == 0) {
    			return permutations;
    		}
    
    		collectPermutations(nums, 0, new ArrayList<>(), permutations);
    		return permutations;
        }
    
    	private void collectPermutations(int[] nums, int start, List<Integer> permutation,
     			List<List<Integer>>  permutations) {
    		
    		if (permutation.size() == nums.length) {
    			permutations.add(permutation);
    			return;
    		}
    
    		for (int i = 0; i <= permutation.size(); i++) {
    			List<Integer> newPermutation = new ArrayList<>(permutation);
    			newPermutation.add(i, nums[start]);
    			collectPermutations(nums, start + 1, newPermutation, permutations);
    		}
    	}
    }
    

    Code flow

    nums = 1,2,3
    
    start = 0, permutation = []
    i = 0, newPermutation = [1]
    	start = 1, permutation = [1]
    	i = 0, newPermutation = [2, 1]
    		start = 2, permutation = [2, 1]
    		i = 0, newPermutation = [3, 2, 1]
    		i = 1, newPermutation = [2, 3, 1]
    		i = 2, newPermutation = [2, 1, 3]
    	i = 1, newPermutation = [1, 2]
    		start = 2, permutation = [1, 2]
    		i = 0, newPermutation = [3, 1, 2]
    		i = 1, newPermutation = [1, 3, 2]
    		i = 2, newPermutation = [1, 2, 3]
    

    Base case and build approach - 524ms

    public class Solution {
       public List<List<Integer>> permute(int[] nums) {
    		return permute(Arrays.stream(nums).boxed().collect(Collectors.toList()));
       }
    
    	private List<List<Integer>> permute(List<Integer> nums) {
    		List<List<Integer>> permutations = new ArrayList<>();
    		if (nums.size() == 0) {
    			return permutations;
    		}
    		if (nums.size() == 1) {
    			List<Integer> permutation = new ArrayList<>();
    			permutation.add(nums.get(0));
    			permutations.add(permutation);
    			return permutations;
    		}
    		
    		List<List<Integer>> smallPermutations = permute(nums.subList(1, nums.size()));
    		int first = nums.get(0);
    		for(List<Integer> permutation : smallPermutations) {
    			for (int i = 0; i <= permutation.size(); i++) {
    				List<Integer> newPermutation = new ArrayList<>(permutation);
    				newPermutation.add(i, first);
    				permutations.add(newPermutation);
    			}
    		}
    		return permutations;
    	}
    }
    

    Code flow

    nums = 1,2,3
    
    smallPermutations(2, 3)
    	smallPermutations(3)
    		return [[3]]
    	first = 2
     		permutation = [3]
    			i = 0, newPermutation = [2, 3]
    			i = 1, newPermutation = [3, 2]
    	return [[2, 3], [3, 2]]
    first = 1
     	permutation = [2, 3]
    		i = 0, newPermutation = [1, 2, 3]
    		i = 1, newPermutation = [2, 1, 3]
    		i = 2, newPermutation = [2, 3, 1]
     	permutation = [3, 2]
    		i = 0, newPermutation = [1, 3, 2]
    		i = 1, newPermutation = [3, 1, 2]
    		i = 2, newPermutation = [3, 2, 1]

  • 0
    C

    thanks for the code flow it is very clear!


Log in to reply
 

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