题解 | #牛群排队#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型二维数组
     */
    private List<int[]> ans = new ArrayList<>();
    private int[] nums;

    public int[][] cow_permute(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        dfs(new int[nums.length], 0);
        int[][] res = new int[ans.size()][];
        return ans.toArray(res);
    }

    private void dfs(int[] path, int idx) {
        if (idx == path.length) {
            ans.add(path);
            return;
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == -1) {
                continue;
            }
            int tmp = nums[i];
            // 将当前元素添加到路径中
            path[idx] = tmp;
            // -1标记为使用
            nums[i] = -1;
            // 递归搜索下一个位置
            dfs(Arrays.copyOfRange(path, 0, nums.length), idx + 1);
            // 回溯，一个是将位置重置为0，未使用
            path[idx] = 0;
            // 回溯，将当前元素进行还原处理
            nums[i] = tmp;
        }
    }
}

本题知识点分析：

1.递归和回溯

2.有序集合的存取

3.API函数进行数组拷贝

4.排序

本题解题思路分析：

1.先进行升序排序

2.利用深度优先搜索

3.编写递归函数，如果已经到数组末尾，添加到集合中

4.-1表示未使用过，如果是-1,说明已经被标记过，continue进行下次循环

5.如果不是-1， 将当前元素添加到路径中

6.递归搜索下一个位置

7.回溯，一个是将位置重置为0，未使用

8.回溯，将当前元素进行还原处理

本题使用编程语言: Java