全排列

给定一个无重复数字的array，求这个数组的全排列
https://leetcode.com/problems/permutations/

递归，一个已经全排列好的数据[2],那么新来一个数字1，就是在已有数组的各个缝隙插入这个1，变成[1,2],[2,1]。同理preArr = [[2,3],[3,2]],$i = 1, 则插入后变成[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]

/**
     * permute
     * @param $nums
     * @return array
     * @brief
     */
    function permute(&$nums) {
        if (!$nums) {
            return [[]];
        }

        //取出数组第一个元素
        $first = array_shift($nums);

        //算余下部分的所有全排列
        $perArr = $this->permute($nums);

        //全排列的过程就是将first值逐渐插入到结果值的空隙中间
        //例如 preArr = [[2,3],[3,2]],$i = 1, 则插入后变成[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]

        foreach ($perArr as &$rVal) {
            //注意这里一定是$i <= count($rVal),不是<，可以用$preArr = [[]]这个做实验，必须是在每个缝隙都插入
            for ($i = 0; $i <= count($rVal); $i++) {
                array_splice($rVal, $i, 0, $first);
                $res[] = $rVal;
                //array 删除第i个元素
                unset($rVal[$i]);
                $rVal = array_values($rVal);
            }
        }
        return $res;
    }

方法二：
另类递归，1，2，3的全排列就是1+2&3的全排列，2+1&3的全排列，3+1&2的全排列，以此类推，这个迭代过程类似求组合的方法，整体迭代比较诡异

 /**
     * permute2
     * @param $nums
     * @return array
     */
    function permute2(&$nums) {
        $res     = [];
        $out     = [];
        $visited = array_fill(0, count($nums) - 1, 0);
        $this->permute2DFS($nums, 0, $visited, $out, $res);
        return $res;
    }

    /**
     * permute2DFS
     * @param $nums
     * @param $level
     * @param $visited
     * @param $out
     * @param $res
     * @return void
     * @brief 函数定义：从第level个数，到这个数组结尾，所有的全排列情况
     */
    function permute2DFS($nums, $level, &$visited, $out, &$res) {
        if ($level == count($nums)) {
            $res[] = $out;
            return;
        }

        foreach ($nums as $k => $v) {
            if ($visited[$k] == 1) {
                continue;
            }
            $visited[$k] = 1;
            $out[]       = $v;
            //从第一个数开始遍历，每个数组合上后面所有的全排列
            //例如[1,2,3],那么就是[1,[2和3的全排列]],[2,[1和3的全排列]],[3,[1和2的全排列]]
            $this->permute2DFS($nums, $level + 1, $visited, $out, $res);
            array_pop($out);
            $visited[$k] = 0;
        }
    }

方法二的Java

    public void nextPermutation(int[] nums) {
        int level = 0;
        List<Integer> out = new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        HashSet<Integer> visited = new HashSet<Integer>();
        this.perMuHelper(nums, level, visited, out, res);
        int a = 1;
    }

    public void perMuHelper(int[] nums, int level, HashSet<Integer> visited, List<Integer> out, List<List<Integer>> res) {
        if (level == nums.length) {
            res.add(new ArrayList<Integer>(out));//需要new啊，否则out这个list就引用进去了
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited.contains(i)) {
                continue;
            }
            visited.add(i);
            out.add(nums[i]);
            this.perMuHelper(nums, level + 1, visited, out, res);
            visited.remove(i);
            out.remove(out.size() - 1);
        }
    }