[LeetCode]--46. Permutations

Given a collection of distinct 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],
  [3,2,1]
]

[LeetCode]–31. Next Permutation

做过这个题之后，肯定启发很多，所以我很快就写出来了。

public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums.length == 0)
            return res;
        Arrays.sort(nums);
        joinlist(nums, res);
        findPermute(nums, res);
        return res;
    }

    private void findPermute(int[] nums, List<List<Integer>> res) {
        int i = nums.length - 1;
        while (i > 0 && nums[i] <= nums[i - 1])
            i--;
        if (i == 0)
            return;
        int second = Integer.MAX_VALUE, secondIndex = Integer.MAX_VALUE;
        for (int j = nums.length - 1; j > i - 1; j--) 
            if (nums[j] > nums[i - 1] && nums[j] < second){
                second = nums[j];
                secondIndex = j;
            }
        int temp = nums[i - 1];
        nums[i - 1] = nums[secondIndex];
        nums[secondIndex] = temp;
        Arrays.sort(nums, i, nums.length);
        joinlist(nums, res);
        findPermute(nums, res);
    }

    private void joinlist(int[] nums, List<List<Integer>> res) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++)
            list.add(nums[i]);
        res.add(list);
    }

找了一个另外的答案，也AC了，但是效率没有我写的高，不过看起来代码简洁一些。可以参考参考。简单理解一下就是找出规律，总共有n！这么多个序列，可以分为(n-1)!这么多个组，每个组n个，这样来通过for循环找到所有答案。

public List<List<Integer>> permute(int[] nums) {
         ArrayList<List<Integer>> rst = new ArrayList<List<Integer>>();
         if (nums == null) {
             return rst; 
         }

         if (nums.length == 0) {
            rst.add(new ArrayList<Integer>());
            return rst;
         }

         ArrayList<Integer> list = new ArrayList<Integer>();
         helper(rst, list, nums);
         return rst;
    }

    public void helper(ArrayList<List<Integer>> rst, ArrayList<Integer> list, int[] nums){
        if(list.size() == nums.length) {
            rst.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(list.contains(nums[i])){
                continue;
            }
            list.add(nums[i]);
            helper(rst, list, nums);
            list.remove(list.size() - 1);
        }

    }