My JAVA recursive solution


  • 0
    Q

    My idea is that Suppose the input is [1, 2, 3], then the result is constructed combining below:
    [1] + permutate([2, 3]) : [1, 2, 3], [1, 3, 2]
    [2] + permutate([1, 3]) : [2, 1, 3], [2, 3, 1]
    [3] + permutate([1, 2]) : [3, 1, 2], [3, 2, 1]

    And code below

        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            int len = nums.length;
    
            if(len == 0){
                return res;
            }
            res = permuteHelper(nums);
            return res;
    
        }
       
        // Recursive 
        private List<List<Integer>> permuteHelper(int[] nums){
            List<List<Integer>> res = new ArrayList<>();
            int len = nums.length;
            if(len == 0){
                return res;
            }
            else if(len == 1){
                List<Integer> list = new ArrayList<>();
                list.add(nums[0]);
                res.add(list);
                return res;
            }
            else{
                for(int index = 0; index < len; index++){
                    int val = nums[index];
                    List<List<Integer>> list = permuteHelper(generateArrays(nums, index));
                    for(int i = 0; i < list.size(); i++){
                        list.get(i).add(0, val);
                    }
                    res.addAll(list);
                }
                return res;
            }
        }
    
        // generate [1, [2, 3]], [2, [1, 3]], [3, [1, 2]]
        private int[] generateArrays(int[] nums, int index){
            int[] res = new int[nums.length - 1];
            for(int i = 0; i < nums.length - 1; i++){
                if(i < index){
                    res[i] = nums[i];
                }
                else{
                    res[i] = nums[i + 1];
                }
            }
            return res;
        }
    

Log in to reply
 

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