全排列问题

全排列问题 问题：         有n个不重复的数，请问全排列共有多少种情况，分别是什么排列顺序？ 一、Java求解全排列问题：         1、回溯算法求解全排列问题：时间复杂度O(n!)

import java.util.*;

public class Main {
    List> res = new linkedList<>();  // 存放所有排列情况的容器

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6};         // n个不重复的数字列表
        Main test_main = new Main();
        test_main.permute(nums);
        System.out.println("该数列的全排列种类数是："+ test_main.res.size());
    }

    public List> permute(int[] nums) {
        // 存放队列情况
        linkedList track = new linkedList<>();
        backtrack(nums, track);
        return res;
    }
    // 排列方式：记录在track中
    // 选择列表：nums中的n个不重复的数字列表
    // 结束条件：nums中的元素全都在track中出现
    private void backtrack(int[] nums, linkedList track) {
        // 触发结束条件，将队列存放进res容器
        if (track.size() == nums.length) {
            res.add(new linkedList<>(track));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 排除已经用过一次的数字
            if (track.contains(nums[i])) {
                continue;
            }
            // 将数字加入排列
            track.add(nums[i]);
            // 进入下一层决策树
            backtrack(nums, track);
            // 取消选择
            track.removeLast();
        }
    }
}

总结：         解决全排列问题用回溯算法，就是个多叉树的遍历问题。