Concise O(n!) Java solution (top solutions are O(n^n)).


  • 1
    D

    The idea is to use the input array to store the current result.
    In every iteration the ith element is fixed.
    I.e. in our first call to the recursive permute function we swap all the elements into the first place once.

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        permute(nums, 0, result);
        return result;
    }
        
    private void permute(int[] nums, int curr, List<List<Integer>> result) {
        if (curr == nums.length) {
            List<Integer> res = new ArrayList<>();
            for (int num: nums) {
                res.add(num);
            }
            result.add(res);
        }
    
        Set<Integer> seen = new HashSet<>();
        for (int i = curr; i < nums.length; i++) {
            if (!seen.contains(nums[i])) {
                swap(nums, curr, i);
                permute(nums, curr + 1, result);
                swap(nums, curr, i);
                seen.add(nums[i]);
            }
        }
    }
        
    private void swap(int[] nums, int i1, int i2) {
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }
    

Log in to reply
 

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