题解 | 没有重复项数字的全排列

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Arrays.sort(num);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < num.length; i++) {
            list.add(num[i]);
        }
        recursion(result, list, 0);
        return result;
    }

    //找每种排序方式 index:坑位的下标
    //思想和数学一样，每个坑位分别放上i位置的数字，然后再换回来
    //保证所有循环的第一层都是[1,2,3]
    public void recursion(ArrayList<ArrayList<Integer>> result,
                          ArrayList<Integer> num, int index) {
        //递归结束条件:index到数组最后
        if (index == num.size() - 1) {
            result.add(new ArrayList<>(num));
            return;
        }

        for (int i = index; i < num.size(); i++) {
            swap(num, i, index);  //把第i个数换到当前index位置固定住
            //继续往后找
            recursion(result, num, index + 1);
            //回溯
            swap(num, i, index);
        }
    }

    public void swap(ArrayList<Integer> num, int i1, int i2) {
        int temp = num.get(i1);
        num.set(i1, num.get(i2));
        num.set(i2, temp);
    }
}