Java solution easy to understand (backtracking)


  • 10
    A

    public class Solution {

    List<List<Integer>> list;
    
    public List<List<Integer>> permute(int[] nums) {
        
        list = new ArrayList<>();
        ArrayList<Integer> perm = new ArrayList<Integer>();
        backTrack(perm,0,nums);
        return list;
    }
    
    void backTrack (ArrayList<Integer> perm,int i,int[] nums){
        
        //Permutation completes
        if(i==nums.length){
            list.add(new ArrayList(perm));
            return;
        }
        
        ArrayList<Integer> newPerm = new ArrayList<Integer>(perm);
        
       //Insert elements in the array by increasing index
        for(int j=0;j<=i;j++){
            newPerm.add(j,nums[i]);
            backTrack(newPerm,i+1,nums);
            newPerm.remove(j);
        }
        
    }
    

    }


  • 0
    H

    Anyone know what's the time O for this solution?


  • 0
    N

    guess its n! time complexity


  • 0
    7

    I think no need to init newPerm


  • 3
    M

    A new ArrayList<Integer> newPerm is not necessary.

    Try this:

    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    permute(new ArrayList<Integer>(), 0, nums, res);
    return res;
    }

    private void permute(ArrayList<Integer> path, int index, int[] nums, List<List<Integer>> res){
        if(index == nums.length){
            res.add(new ArrayList<Integer>(path));
            return;
        }
        
        for(int j = 0; j <=index; ++j ){
            path.add(j, nums[index]);
            permute(path, index + 1, nums, res);
            path.remove(j);
        }
    }

Log in to reply
 

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