My Java solution, 4ms, with additional space cost


  • 1
    A
    public class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            List<Integer> numbers = new ArrayList<Integer>();
            for(int i=0; i<nums.length; i++){
                numbers.add(nums[i]);
            }
            dfs(res, nums.length, numbers, new ArrayList<Integer>());
            return res;
        }
        
        public void dfs(List<List<Integer>> res, int length, List<Integer> numList, List<Integer> list){
            if(list.size()==length){
                res.add(new ArrayList(list));
                return;
            }
            for(int i=0; i<numList.size(); i++){
                List<Integer> newList = new ArrayList<>(list);
                newList.add(numList.get(i));
                List<Integer> newNumList = new ArrayList<>(numList);
                newNumList.remove(i);
                dfs(res, length, newNumList, newList);
            }
            
        }
    }
    

  • 0
    A

    @aixinjueluoqi
    My solution to Permutations II

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            List<Integer> numbers = new ArrayList<Integer>();
            Arrays.sort(nums);
            for(int i=0; i<nums.length; i++){
                numbers.add(nums[i]);
            }
            dfs(res, nums.length, numbers, new ArrayList<Integer>());
            return res;
        }
        
        public void dfs(List<List<Integer>> res, int length, List<Integer> numList, List<Integer> list){
            if(list.size()==length){
                res.add(new ArrayList(list));
                return;
            }
            for(int i=0; i<numList.size(); i++){
                if(i!=0 && numList.get(i)==numList.get(i-1)) continue;
                List<Integer> newList = new ArrayList<>(list);
                newList.add(numList.get(i));
                List<Integer> newNumList = new ArrayList<>(numList);
                newNumList.remove(i);
                dfs(res, length, newNumList, newList);
            }
            
        }
    }
    

Log in to reply
 

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