Permutations

描述​

Given a collection of numbers, return all possible permutations.

For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

代码​

递归​

// Permutations// Recursive// Time Complexity: O(n!), Space Complexity: O(n)public class Solution {    public List<List<Integer>> permute(int[] nums) {        Arrays.sort(nums);        List<List<Integer>> result = new ArrayList<>();        dfs(nums, 0, result);        return result;    }    private static void dfs(int[] nums, int start, List<List<Integer>> result) {        if (start == nums.length) {            result.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));            return;        }        for (int i = start; i < nums.length; i++) {            swap(nums, start, i);            dfs(nums, start + 1, result);            swap(nums, start, i); // restore        }    }    private static void swap(int[] nums, int i, int j) {        int tmp = nums[i];        nums[i] = nums[j];        nums[j] = tmp;    }}

next_permutation()​

// Permutations// 重新实现 next_permutation()// 时间复杂度O(n!)，空间复杂度O(1)public class Solution {    public List<List<Integer>> permute(int[] nums) {        List<List<Integer>> result = new ArrayList<>();        Arrays.sort(nums);        do {            ArrayList<Integer> one = new ArrayList<>();            for (int i : nums) {                one.add(i);            }            result.add(one);            // 调用的是 2.1.12 节的 next_permutation()            // 而不是 std::next_permutation()        } while(nextPermutation(nums, 0, nums.length));        return result;    }    // 代码来自 2.1.12 节的 next_permutation()    private static boolean nextPermutation(int[] nums, int begin, int end) {        // From right to left, find the first digit(partitionNumber)        // which violates the increase trend        int p = end - 2;        while (p > -1 && nums[p] >= nums[p + 1]) --p;        // If not found, which means current sequence is already the largest        // permutation, then rearrange to the first permutation and return false        if(p == -1) {            reverse(nums, begin, end);            return false;        }        // From right to left, find the first digit which is greater        // than the partition number, call it changeNumber        int c = end - 1;        while (c > 0 && nums[c] <= nums[p]) --c;        // Swap the partitionNumber and changeNumber        swap(nums, p, c);        // Reverse all the digits on the right of partitionNumber        reverse(nums, p+1, end);        return true;    }    private static void swap(int[] nums, int i, int j) {        int tmp = nums[i];        nums[i] = nums[j];        nums[j] = tmp;    }    private static void reverse(int[] nums, int begin, int end) {        end--;        while (begin < end) {            swap(nums, begin++, end--);        }    }}