Java 4ms Solution: Beats 99.82%


  • 0
    H
    public class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if(nums == null || nums.length == 0) return res;
            permuteHelper(nums, 0, res);
            return res;
        }
        
        public void permuteHelper(int[] nums, int index, List<List<Integer>> list) {
            if(index >= nums.length-1) {
                //done with the current permutation. add the current array to the list
                List<Integer> temp = new ArrayList<>();
                for(int n : nums) {
                    temp.add(n);
                }
                list.add(temp);
                return;
            }
            //permute nums[index...nums.length-1]
            for(int i = index; i<nums.length; i++) {
                //swap the index-th number with the i-th number
                int t = nums[index];
                nums[index] = nums[i];
                nums[i] = t;
                
                //recurse for nums[index+1,nums.length-1]
                permuteHelper(nums, index+1, list);
                
                //swap back the number
                t = nums[index];
                nums[index] = nums[i];
                nums[i] = t;
            }
        }
    }
    

  • 0
    H

    More compact code:

    public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if(nums == null || nums.length == 0) return res;
            List<Integer> intList = new ArrayList<>();
            for (int i : nums) intList.add(i);
            permuteHelper(intList, 0, res);
            return res;
        }
        
        public void permuteHelper(List<Integer> nums, int element, List<List<Integer>> list) {
            if (element == nums.size() - 1) {
                list.add(new ArrayList(nums));
                return;
            }
            for (int i = element; i < nums.size(); i++) {
               Collections.swap(nums, i, element);
               permuteHelper(nums, element + 1, list);
               Collections.swap(nums, element, i);
            }
            
        }
    

Log in to reply
 

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