Simple Java Backtracking Solution.


  • 2
    S

    The idea is to keep the current element at index and retrieve the solution for index +1.
    The solution for index+1 is 'prev'.
    Then iterate all lists in that solution and add the current element at every possible index in that solution.

    public class Solution {
        public List<List<Integer>> permute(int[] nums) {
            return helper(nums, 0);
        }
        
        List<List<Integer>> helper(int[] nums, int index){
            List<List<Integer>> result=new ArrayList();
            if(index==nums.length){
                List<Integer> curr=new ArrayList();
                result.add(curr);
                return result;
            }
    
            List<List<Integer>> prev=helper(nums,index+1);
            for(List<Integer> list: prev){
                for(int i=0; i<=list.size(); i++){
                    List<Integer> listNew=new ArrayList(list);
                    listNew.add(i,nums[index]);
                    result.add(listNew);
                }
            }   
            
            return result;
        }
    }

Log in to reply
 

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