Java solution based on next permutation, no extra space


  • 0
    T
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        while (true) {
            List<Integer> res = new ArrayList<Integer>();
            for (int n : num)
                res.add(n);
            if (!result.isEmpty() && res.equals(result.get(0)))
                break;
            result.add(res);
            nextPermutation(num);
        }
        return result;
    }
    
    public void nextPermutation(int[] num) {
        int n = num.length;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (num[j] > num[i]) {
                    int temp = num[j];
                    num[j] = num[i];
                    num[i] = temp;
                    reverse(num, i + 1, n - 1);
                    return;
                }
            }
        }
        reverse(num, 0, n - 1);
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }

Log in to reply
 

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