初始时选择第0索引结点 选择第i个元素之后形成的父节点，父节点的孩子结点，通过父结点的第i和第j元素交换，轮流把第j个元素放到第i位，形成子结点

package xcrj.kchalgorithm.backtracking;

import java.util.Arrays;

/**
 * 排列树
 * 达到要求的排列，所有元素都在；把那个元素放到第1位，把那个元素放到第2位，依次类推
 * <p>
 * 选择第i个元素之后形成的父节点，父节点的孩子结点，通过父结点的第i和第j元素交换，轮流把第j个元素放到第i位，形成子结点
 */
public class PermutationTree {
          
   
    /**
     * @param xs
     * @param i
     * @param len
     */
    public static void permutationTree(int[] xs, int i, int len) {
          
   
        // 到达叶子结点输出
        if (i == len) {
          
   
            System.out.println(Arrays.toString(xs));
        }
        // 到达非叶子结点，生成i结点的所有孩子结点j
        else {
          
   
            // ！选择第i个元素之后形成的父节点，父节点的孩子结点，通过父结点的第i和第j元素交换，轮流把第j个元素放到第i位，形成子结点
            for (int j = i; j < len; j++) {
          
   
                // 交换，通过父结点的第i和第j元素交换，轮流把第j个元素放到第i位，形成子结点
                int temp = xs[j];
                xs[j] = xs[i];
                xs[i] = temp;
                // 深度优先遍历操作孩子结点
                permutationTree(xs, i + 1, len);
                // 交换回来
                int temp2 = xs[j];
                xs[j] = xs[i];
                xs[i] = temp2;
            }
        }
    }

    public static void main(String[] args) {
          
   
        int[] xs = {
          
   1, 2, 3};
        permutationTree(xs, 0, xs.length);
    }
}

时间复杂度

O ( n ! ) O(n!) O(n!) 第0层 第1层：第1位有n种选择 第2层：第2位有n-1种选择（第1位的数字已经确定） 第3层：第3位有n-2种选择 … 第n层：第n位有1种选择

要得到1个完整的排列，从根到叶子一步步完成，所以时间复杂度是 O ( n ! ) O(n!) O(n!)